5.5: More on GCD
( \newcommand{\kernel}{\mathrm{null}\,}\)
In this section, we shall discuss a few technical results about gcd(a,b).
Theorem 5.5.1
Let d=gcd(a,b), where a,b∈N. Then {as+bt∣s,t∈Z}={nd∣n∈Z}. Hence, every linear combination of a and b is a multiple of gcd(a,b), and vice versa, every multiple of gcd(a,b) is expressible as a linear combination of a and b.
- Proof
-
For brevity, let S={as+bt∣s,t∈Z},andT={nd∣n∈Z}. We shall show that S=T by proving that S⊆T and T⊆S.
Let x∈S. To prove that S⊆T, we want to show that x∈T as well. Being in S means x=as+bt for some integers s and t. Since d=gcd(a,b), we know that d∣a and d∣b. Hence, a=da′ and b=db′ for some integers a′ and b′. Then x=as+bt=da′s+db′t=d(a′s+b′t), where a′s+b′t is an integer. This shows that x is a multiple of d. Hence, x∈T.
To show that T⊆S, it suffices to show that d∈S. The reason is, if d=as+bt for some integers s and t, then nd=n(as+bt)=a(ns)+b(nt) implies that nd∈S.
To prove that d∈S, consider S+. Since a=a⋅1+b⋅0, we have a∈S+. Hence, S+ is a nonempty set of positive integers. The principle of well-ordering implies that S+ has a smallest element. Call it e. Then e=as∗+bt∗ for some integers s∗ and t∗. We already know that a∈S+. Being the smallest element in S+, we must have e≤a. Then a=eq+r for some integers q and r, where 0≤r<e. If r>0, then r=a−eq=a−(as∗+bt∗)q=a(1−s∗q)+b(−t∗q). This makes r a linear combination of a and b. Since r>0, we find r∈S+. Since r<e would contradict the minimality of e, we must have r=0. Consequently, a=eq, thus e∣a. Similarly, since b=a⋅0+b⋅1∈S+, we can apply the same argument to show that e∣b. We conclude that e is a common divisor of a and b.
Let f be any common divisor of a and b. Then f∣a and f∣b. It follows that f∣(ax+by) for any integers x and y. In particular, f∣(as∗+bt∗)=e. Hence, f≤e. Since e is itself a common divisor of a and b, and we have just proved that e is larger than any other common divisor of a and b, the integer e itself must be the greatest common divisor. It follows that d=gcd(a,b)=e∈S+. The proof is now complete.
Corollary 5.5.2
The greatest common divisor of two nonzero integers a and b is the smallest positive integer among all their linear combinations. In other words, gcd(a,b) is the smallest positive element in the set {as+bt∣s,t∈Z}.
Corollary 5.5.3
For any nonzero integers a and b, there exist integers s and t such that gcd(a,b)=as+bt.
- Proof
-
Theorem 5.5.1 maintains that the set of all the linear combinations of a and b equals to the set of all the multiples of gcd(a,b). Since gcd(a,b) is a multiple of itself, it must equal to one of those linear combinations. Thus, gcd(a,b)=sa+tb for some integers s and t.
Theorem 5.5.4
Two nonzero integers a and b are relatively prime if and only if as+bt=1 for some integers s and t.
- Proof
-
The result is a direct consequence of the definition that a and b are said to be relatively prime if gcd(a,b)=1.
Example 5.5.1
It is clear that 5 and 7 are relatively prime, so are 14 and 27. Find the linear combination of these two pairs of numbers that equals to 1.
- Solution
-
By inspection, or using the extended Euclidean algorithm, we find 3⋅5−2⋅7=1, and 2⋅14−1⋅27=1.
hands-on Exercise 5.5.1
Show that gcd(133,143)=1 by finding an appropriate linear combination.
hands-on Exercise 5.5.2
Show that 757 and 1215 are relatively prime by finding an appropriate linear combination.
Example 5.5.2
It follows from (−1)⋅n+1⋅(n+1)=1 that gcd(n,n+1)=1. Thus, any pair of consecutive positive integers is relatively prime.
Theorem 5.5.5 (Euclid's Lemma)
Let a,b,c∈Z. If gcd(a,c)=1 and c∣ab, then c∣b.
Discussion
Let us write down what we know and what we want to show (WTS): Know:as+ct=1 for some integers s and t,ab=cx for some integer x,WTS:b=cq for some integer q. To be able to show that b=cq for some integer q, we have to come up with some information about b. This information must come from the two equations as+ct=1 and ab=cx. Since b=b⋅1, we can multiply b to both sides of as+ct=1. By convention, we cannot write
(as+ct=1)⋅b.
This notation is unacceptable! The reason is: we cannot multiply an equation by a number. Rather, we have to multiply both sides of an equation by the number: b=1⋅b=(as+ct)⋅b=asb+ctb. Obviously, ctb is a multiple of c; we are one step closer to our goal. Since asb=ab⋅s, and we do know that ab is indeed a multiple of c, so the proof can be completed. We are now ready to tie up the loose ends, and polish up the proof.
- Proof
-
Assume gcd(a,c)=1, and c∣ab. There exist integers s and t such that as+ct=1. This leads to b=1⋅b=(as+ct)⋅b=asb+ctb. Since c∣ab, there exists an integer x such that ab=cx. Then b=ab⋅s+ctb=cx⋅s+ctb=c(xs+tb), where xc+tb∈Z. Therefore, c∣b.
Corollary 5.5.6
If a,b∈Z and p is a prime such that p∣ab, then either p∣a or p∣b.
- Proof
-
If p∣a, we are done with the proof. If p∤, then \gcd(p,a)=1, and Euclid’s lemma implies that p\mid b.
We cannot apply the corollary if p is composite. For instance, 6\mid 4\cdot15, but 6\nmid 4 and 6\nmid 15. On the other hand, when p\mid ab, where p is a prime, it is possible to have both p\mid a and p\mid b. For instance, 5\mid 15\cdot 25, yet we have both 5\mid 15 and 5\mid 25.
Corollary \PageIndex{7}
If a_1,a_2,\ldots,a_n\in\mathbb{Z} and p is a prime such that p\mid a_1 a_2 \cdots a_n, then p\mid a_i for some i, where 1\leq i\leq n. Consequently, if a prime p divides a product of n factors, then p must divide at least one of these n factors.
- Proof
-
We leave the proof to you as an exercise.
Example \PageIndex{3}\label{eg:moregcd-03}
Prove that \sqrt{2} is irrational.
Remark
We proved previously that \sqrt{2} is irrational in a hands-on exercise. The solution we presented has a minor flaw. A key step in that proof claims that \mbox{The integer 2 divides $m^2$, therefore 2 divides $m$}. \nonumber This claim is false in general. For example, 4 divides 6^2, but 4 does not divide 6. Therefore, we have to justify why this claim is valid for 2.
- Solution
-
Suppose \sqrt{2} is rational, then we can write \sqrt{2} = \frac{m}{n} \nonumber for some positive integers m and n that do not share any common divisor except 1. Squaring both sides and cross-multiplying gives 2n^2 = m^2. \nonumber Thus 2 divides m^2. Since 2 is prime, Euclid’s lemma implies that 2 must also divide m. Then we can write m=2s for some integer s. The equation above becomes 2n^2 = m^2 = (2s)^2 = 4s^2. \nonumber Hence, n^2 = 2s^2, \nonumber which implies that 2 divides n^2. Again, since 2 is prime, Euclid’s lemma implies that 2 also divides n. We have proved that both m and n are divisible by 2. This contradicts the assumption that m and n do not share any common divisor. Hence, \sqrt{2} must be irrational.
hands-on Exercise \PageIndex{3}\label{he:moregcd-03}
Prove that \sqrt{7} is irrational.
We close this section with a truly fascinating result.
Theorem \PageIndex{8}
For any positive integers m and n, \gcd(F_m,F_n)=F_{\gcd(m,n)}.
Corollary \PageIndex{9}
For any positive integer n, 3\mid F_n \Leftrightarrow 4\mid n.
- Proof
-
(\Rightarrow) If 3\mid F_n, then, because F_3=4, we have 3 = \gcd(3,F_n) = \gcd(F_4,F_n) = F_{\gcd(4,n)}. \nonumber It follows that \gcd(4,n)=4, which in turn implies that 4\mid n.
(\Leftarrow) If 4\mid n, then \gcd(4,n)=4, and \gcd(3,F_n) = \gcd(F_4,F_n) = F_{\gcd(4,n)} = F_4 = 3; \nonumber therefore, 3\mid F_n.
Summary and Review
- Given any two nonzero integers, there is only one special linear combination that would equal to their greatest common divisor.
- All other linear combinations are only multiples of their greatest common divisor.
- If a and c are relatively prime, then Euclid’s lemma asserts that if c divides ab, then c must divide b.
- In particular, if p is prime, and if p\mid ab, then either p\mid a or p\mid b.
Exercise \PageIndex{1}\label{ex:moregcd-01}
Given any arbitrary positive integer n, prove that 2n+1 and 3n+2 are relatively prime.
Exercise \PageIndex{2}\label{ex:moregcd-02}
Use induction to prove that for any integer n\geq2, if a_1,a_2,\ldots,a_n\in\mathbb{Z} and p is a prime such that p\mid a_1 a_2 \cdots a_n, then p\mid a_i for some i, where 1\leq i\leq n.
Exercise \PageIndex{3}\label{ex:moregcd-03}
Prove that \sqrt{p} is irrational for any prime number p.
Exercise \PageIndex{4}\label{ex:moregcd-04}
Prove that \sqrt[3]{2} is irrational.
Exercise \PageIndex{5}\label{ex:moregcd-05}
Given any arbitrary positive integers a, b, and c, show that if a\mid c, b\mid c, and \gcd(a,b)=1, then ab\mid c.
Remark. This result is very important. Remember it!
Exercise \PageIndex{6}\label{ex:moregcd-06}
Given any arbitrary positive integers a, b, and c, show that if a\mid c, and b\mid c, then ab\mid cd, where d=\gcd(a,b).
Exercise \PageIndex{7}\label{ex:moregcd-07}
Use induction to prove that 3\mid(2^{4n}-1) and 5\mid(2^{4n}-1) for any integer n\geq1. Use these results to prove that 15\mid (2^{4n}-1) for any integer n\geq1.
Exercise \PageIndex{8}\label{ex:moregcd-08}
Prove that 2\mid F_n \Leftrightarrow 3\mid n for any positive integer n.