Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

4.4: Relatively Prime numbers

( \newcommand{\kernel}{\mathrm{null}\,}\)

Definition: Relatively prime or Coprime

Two integers are relatively prime or Coprime when there are no common factors other than 1. This means that no other integer could divide both numbers evenly. Two integers a,b are called relatively prime to each other if gcd(a,b)=1.

For example, 7 and 20 are relatively prime.

Theorem

Let a,bZ. If there exist integers x and y such that ax+by=1 then gcd(a,b)=1.

Proof:

Let a,bZ, such that d= gcd(a,b). Then d|a and d|b.

Hence d|(ax+by), thus d|1. Which implies d=±1, since gcd is the greatest, d=1.

Example 4.4.1:

Suppose a and b are relatively prime integers. Prove that gcd(a+b,ab)=1, or 2.

Solution

Let a and b be relatively prime integers. Then gcd(a,b)=1. Suppose d=gcd(a+b,ab). Then d|(a+b) and d|(ab). Then a+b=dm and ab=dn for some m,nZ. Now 2a=d(m+n) and 2b=d(mn). Thus d|2a and d|2b. Hence d|gcd(2a,2b). Since gcd(2a,2b)=2gcd(a,b). d|2. Thus d=1 or 2.

 

Example 4.4.2:

Suppose a and c are relatively prime integers and b is an integer such that b|c. Prove that gcd(a,b)=1.

Solution

Let a and c be relatively prime integers. Then gcd(a,c)=1. Thus there exist integers x and y such that ax+cy=1. Suppose b is an integer such that b|c. Then c=bm for some mZ. Now ax+bmy=1. Therefore, gcd(a,b)=1.

Multiplicative inverse modulo m

Let mZ+.  Let aZ such that a and m are relatively prime. Then there exist integers x and y such that ax+my=1. Then  ax1(modm). Note that 1 is the multiplicative identity on modm. In this case, x(modm) is the inverse of a(modm).

Example 4.4.3

If possible, find multiplicative inverse of 2(mod10).

Solution

Since gcd(2,10)=21, 2 has no multiplicative inverse modulo 10.

Example 4.4.4

If possible, find multiplicative inverse of 16(mod35).

Solution

By using Euclidean Algorithm, we will find gcd(16,35).

35=(16)(2)+316=(3)(5)+13=(1)(3)+0

Thus gcd(16,35)=1. Hence multiplicative inverse of 16(mod35) exists.

By using Bezout's algorithm,

1=16+(3)(5)=16+(35+(16)(2))(5)=(35)(5)+(16)(11)

Thus gcd(16,35)=1=(35)(5)+(16)(11). Hence the multiplicative inverse of 16(mod35) is 11.

 


4.4: Relatively Prime numbers is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by LibreTexts.

Support Center

How can we help?