5.5: More on GCD

Last updated
Save as PDF

Page ID: 8411

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

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

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

In this section, we shall discuss a few technical results about $\gcd(a,b)$.

Theorem $\PageIndex{1}\label{thm:EA}$

Let $d=\gcd(a,b)$, where $a,b\in\mathbb{N}$. Then \[\{ as+bt \mid s,t\in\mathbb{Z} \} = \{ nd \mid n\in\mathbb{Z} \}. \nonumber\] 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\mid s,t\in\mathbb{Z}\}, \qquad\mbox{and}\qquad T=\{nd\mid n\in\mathbb{Z}\}. \nonumber\] We shall show that $S=T$ by proving that $S\subseteq T$ and $T\subseteq S$.

Let $x\in S$. To prove that $S\subseteq T$, we want to show that $x\in 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\mid a$ and $d\mid 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), \nonumber\] where $a's+b't$ is an integer. This shows that $x$ is a multiple of $d$. Hence, $x\in T$.

To show that $T\subseteq S$, it suffices to show that $d\in 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\in S$.

To prove that $d\in S$, consider $S^+$. Since $a=a\cdot1+b\cdot0$, we have $a\in 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^* \nonumber\] for some integers $s^*$ and $t^*$. We already know that $a\in S^+$. Being the smallest element in $S^+$, we must have $e\leq a$. Then $a=eq+r$ for some integers $q$ and $r$, where $0\leq r<e$. If $r>0$, then \[r = a-eq = a-(as^*+bt^*)q = a(1-s^*q)+b(-t^*q). \nonumber\] This makes $r$ a linear combination of $a$ and $b$. Since $r>0$, we find $r\in S^+$. Since $r<e$ would contradict the minimality of $e$, we must have $r=0$. Consequently, $a=eq$, thus $e\mid a$. Similarly, since $b = a\cdot0+b\cdot1\in S^+$, we can apply the same argument to show that $e\mid 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\mid a$ and $f\mid b$. It follows that $f\mid (ax+by)$ for any integers $x$ and $y$. In particular, $f\mid(as^*+bt^*)=e$. Hence, $f\leq 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\in S^+$. The proof is now complete.

Corollary $\PageIndex{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 \mid s,t\in\mathbb{Z}\}$.

Corollary $\PageIndex{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 $\PageIndex{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 $\PageIndex{1}\label{eg:moregcd-01}$

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\cdot5-2\cdot7=1$, and $2\cdot14-1\cdot27=1$.

hands-on Exercise $\PageIndex{1}\label{he:moregcd-01}$

Show that $\gcd(133,143)=1$ by finding an appropriate linear combination.

hands-on Exercise $\PageIndex{2}\label{he:moregcd-02}$

Show that 757 and 1215 are relatively prime by finding an appropriate linear combination.

Example $\PageIndex{2}\label{eg:moregcd-02}$

It follows from \[(-1)\cdot n+1\cdot(n+1) = 1 \nonumber\] that $\gcd(n,n+1)=1$. Thus, any pair of consecutive positive integers is relatively prime.

Theorem $\PageIndex{5}$ (Euclid's Lemma)

Let $a,b,c\in\mathbb{Z}$. If $\gcd(a,c)=1$ and $c\mid ab$, then $c\mid b$.

Discussion

Let us write down what we know and what we want to show (WTS): \[\begin{array}{ll} \mbox{Know}: & as+ct=1 \mbox{ for some integers $s$ and $t$}, \\ & ab = cx \mbox{ for some integer $x$}, \\ \mbox{WTS}: & b = cq \mbox{ for some integer $q$}. \end{array} \nonumber\] 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\cdot1$, we can multiply $b$ to both sides of $as+ct=1$. By convention, we cannot write

$(as+ct=1) \cdot 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\cdot b = (as+ct)\cdot b = asb + ctb. \nonumber\] Obviously, $ctb$ is a multiple of $c$; we are one step closer to our goal. Since $asb = ab\cdot 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\mid ab$. There exist integers $s$ and $t$ such that \[as + ct = 1. \nonumber\] This leads to \[b = 1\cdot b = (as+ct)\cdot b = asb + ctb. \nonumber\] Since $c\mid ab$, there exists an integer $x$ such that $ab=cx$. Then \[b = ab\cdot s + ctb = cx\cdot s + ctb = c(xs+tb), \nonumber\] where $xc+tb\in\mathbb{Z}$. Therefore, $c\mid b$.

Corollary $\PageIndex{6}$

If $a,b\in\mathbb{Z}$ and $p$ is a prime such that $p\mid ab$, then either $p\mid a$ or $p\mid b$.

Proof: If $p\mid a$, we are done with the proof. If $p\nmid a$, 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$.

Search

Text Color

Text Size

Margin Size

Font Type