1.6: Greatest Common Divisor
- Page ID
- 82288
\( \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}\)Definition \(\PageIndex{1}\)
Let \(a,b\in\mathbb{Z}\). If \(a\ne 0\) or \(b\ne 0\), we define \(\gcd(a,b)\) to be the largest integer \(d\) such that \(d\mid a\) and \(d\mid b\). We define \(\gcd(0,0)=0\).
Discussion
If \(e\mid a\) and \(e\mid b\) we call \(e\) a common divisor of \(a\) and \(b\). Let \[C(a,b)=\{e:e\mid a\text{ and }e\mid b\},\nonumber\] that is, \(C(a,b)\) is the set of all common divisors of \(a\) and \(b\). Note that since everything divides \(0\) \[C(0,0)=\mathbb{Z}\nonumber\] so there is no largest common divisor of \(0\) with \(0\). This is why we must define \(\gcd(0,0)=0\).
Example \(\PageIndex{1}\)
\[C(18,30)=\{-1,1,-2,2,-3,3,-6,6\}.\nonumber\] So \(\gcd(18,30)=6\).
Lemma \(\PageIndex{1}\)
If \(e\mid a\) then \(-e\mid a\).
- Proof
-
If \(e\mid a\) then \(a=ek\) for some \(k\). Then \(a=(-e)(-k)\). Since \(-e\) and \(-k\) are also integers \(-e\mid a\).
If \(a\ne 0\), the largest positive integer that divides \(a\) is \(|a|\).
- Proof
-
Recall that \[|a|=\left\{\begin{array}{ccc} a & \text{if} & a\ge 0 \\ -a & \text{if} & a<0. \end{array}\right.\nonumber\] First note that \(|a|\) actually divides \(a\): If \(a>0\), since we know \(a\mid a\) we have \(|a|\mid a\). If \(a<0\), \(|a|=-a\). In this case \(a=(-a)(-1)=|a|(-1)\) so \(|a|\) is a factor of \(a\). So, in either case \(|a|\) divides \(a\), and in either case \(|a|>0\), since \(a\ne 0\).
Now suppose \(d\mid a\) and \(d\) is positive. Then \(a=dk\) some \(k\) so \(-a=d(-k)\) for some \(k\). So \(d\mid |a|\). So by Theorem 3.1 (10) we have \(d\le|a|\).
The following lemma shows that in computing \(\gcd\)’s we may restrict ourselves to the case where both integers are positive.
Lemma \(\PageIndex{3}\)
\(\gcd(a,b)=\gcd(|a|,|b|)\).
- Proof
-
If \(a=0\) and \(b=0\), we have \(|a|=a\) and \(|b|=b\). So \(\gcd(a,b)=\gcd(|a|,|b|)\). Suppose one of \(a\) or \(b\) is not \(0\). Note that \(d\mid a\Leftrightarrow d\mid |a|\). See Exercise \(\PageIndex{1}\). It follows that \[C(a,b)=C(|a|,|b|).\nonumber\] So the largest common divisor of \(a\) and \(b\) is also the largest common divisor of \(|a|\) and \(|b|\).
Prove that \[d\mid a\Leftrightarrow d\mid |a|\nonumber\]
- Hint
-
Recall that \(|a|=a\) if \(a\ge 0\) and \(|a|=-a\) if \(a<0\). So you need to consider two cases.
Lemma \(\PageIndex{4}\)
\(\gcd(a,b)=\gcd(b,a)\).
- Proof
-
Clearly \(C(a,b)=C(b,a)\). It follows that the largest integer in \(C(a,b)\) is the largest integer in \(C(b,a)\), that is, \(\gcd(a,b)=\gcd(b,a)\).
Lemma \(\PageIndex{5}\)
If \(a\ne 0\) and \(b\ne 0\), then \(\gcd(a,b)\) exists and satisfies \[0<\gcd(a,b)\le\min\{|a|,|b|\}.\nonumber\]
- Proof
-
Note that \(\gcd(a,b)\) is the largest integer in the set \(C(a,b)\) of common division of \(a\) and \(b\). Since \(1\mid a\) and \(1\mid b\) we know that \(1\in C(a,b)\). So the largest common divisor must be at least \(1\) and is therefore positive. On the other hand \(d\in C(a,b)\Rightarrow d\mid |a|\) and \(d\mid |b|\) so \(d\) is no larger than \(|a|\) and no larger than \(|b|\). So \(d\) is at most the smaller of \(|a|\) and \(|b|\). Hence \(\gcd(a,b)\le\min\{|a|,|b|\}\).
From the above lemmas we have \[\begin{split} \gcd(48,732) &=\gcd(-48,732) \\ &=\gcd(-48,-732) \\ &=\gcd(48,-732). \end{split}\nonumber\] We also know that \[0<\gcd(48,732)\le 48.\nonumber\] Since if \(d=\gcd(48,732)\), then \(d\mid 48\), to find \(d\) we may check only which positive divisors of \(48\) also divide \(732\).
Exercise \(\PageIndex{2}\)
Find \(\gcd(48,732)\) using Example \(\PageIndex{2}\).
Exercise \(\PageIndex{3}\)
Find \(\gcd(a,b)\) for each of the following values of \(a\) and \(b\):
- \(a=-b\), \(b=14\)
- \(a=-1\), \(b=78654\)
- \(a=0\), \(b=-78\)
- \(a=2\), \(b=-786541\)