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,b∈Z. If there exist integers x and y such that ax+by=1 then gcd(a,b)=1.
Proof:
Let a,b∈Z, 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,a−b)=1, or 2.
Solution
Let a and b be relatively prime integers. Then gcd(a,b)=1. Suppose d=gcd(a+b,a−b). Then d|(a+b) and d|(a−b). Then a+b=dm and a−b=dn for some m,n∈Z. Now 2a=d(m+n) and 2b=d(m−n). 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 m∈Z. Now ax+bmy=1. Therefore, gcd(a,b)=1.
Multiplicative inverse modulo m
Let m∈Z+. Let a∈Z such that a and m are relatively prime. Then there exist integers x and y such that ax+my=1. Then ax≡1(modm). Note that 1 is the multiplicative identity on modm. In this case, x(modm) is the inverse of a(modm).
If possible, find multiplicative inverse of 2(mod10).
Solution
Since gcd(2,10)=2≠1, 2 has no multiplicative inverse modulo 10.
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.