Loading [MathJax]/jax/element/mml/optable/MathOperators.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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,bN. Then {as+bts,tZ}={ndnZ}. 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+bts,tZ},andT={ndnZ}. We shall show that S=T by proving that ST and TS.

Let xS. To prove that ST, we want to show that xT as well. Being in S means x=as+bt for some integers s and t. Since d=gcd(a,b), we know that da and db. Hence, a=da and b=db for some integers a and b. Then x=as+bt=das+dbt=d(as+bt), where as+bt is an integer. This shows that x is a multiple of d. Hence, xT.

To show that TS, it suffices to show that dS. The reason is, if d=as+bt for some integers s and t, then nd=n(as+bt)=a(ns)+b(nt) implies that ndS.

To prove that dS, consider S+. Since a=a1+b0, we have aS+. 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 aS+. Being the smallest element in S+, we must have ea. Then a=eq+r for some integers q and r, where 0r<e. If r>0, then r=aeq=a(as+bt)q=a(1sq)+b(tq). This makes r a linear combination of a and b. Since r>0, we find rS+. Since r<e would contradict the minimality of e, we must have r=0. Consequently, a=eq, thus ea. Similarly, since b=a0+b1S+, we can apply the same argument to show that eb. We conclude that e is a common divisor of a and b.

Let f be any common divisor of a and b. Then fa and fb. It follows that f(ax+by) for any integers x and y. In particular, f(as+bt)=e. Hence, fe. 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)=eS+. 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+bts,tZ}.

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 3527=1, and 214127=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,cZ. If gcd(a,c)=1 and cab, then cb.

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=b1, 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=1b=(as+ct)b=asb+ctb. Obviously, ctb is a multiple of c; we are one step closer to our goal. Since asb=abs, 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 cab. There exist integers s and t such that as+ct=1. This leads to b=1b=(as+ct)b=asb+ctb. Since cab, there exists an integer x such that ab=cx. Then b=abs+ctb=cxs+ctb=c(xs+tb), where xc+tbZ. Therefore, cb.

Corollary 5.5.6

If a,bZ and p is a prime such that pab, then either pa or pb.

Proof

If pa, 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.


This page titled 5.5: More on GCD is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

  • Was this article helpful?

Support Center

How can we help?