1.2: Greatest common divisor and least common multiple
- Page ID
- 131032
\( \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}\)Think out loud
We want to tile a \(253\) ft by \(123\) ft (\(a=253\) and \(b=123,\) with \(a, b \in \mathbb{Z} \)) floor with identical square tiles. What is the largest square tile we can use?
Definition: Greatest Common Divisor
Let \(a,b \in \mathbb{Z}\), where not both \(a,b\) is zero.
Then, we say that an integer \(d=\gcd(a,b) \in \mathbb{Z_+}\)., greatest common divisor if it satisfies the following conditions:
-
\(d|a\) and \(d|b\), Note: \(d\) must divide both numbers
2. If \(c \in \mathbb{Z}\), \(c|a\) and \(c|b\) then \(c\le d\). Note: \(d\) is the greatest number divides both.
Thus, the greatest common divisor of two integers \(a\) and \(b\), also known as GCD of \(a\) and \(b\), is the greatest positive integer that divides both the integers \(a\) and \(b\). This class will use the following notation: \(\gcd (a,b)\).
Example \(\PageIndex{1}\):
What is the \(\gcd\) of \(15\) and \(20\)?
A process to find the solution:
List all positive divisors of \(15\) and \(20\).
The positive divisors of \(15\) are \(1, 3, 5,\) and \(15\).
The positive divisors of \(20\) are \(1, 2, 4, 5, 10,\) and \(20\).
The common positive divisors are \(1, 5\).
As you can see from the list the gcd of \(15\) and \(20\) is \(5.\) That is, the \( \gcd(15, 20)=5.\)
Example \(\PageIndex{2}\):
An elementary gym teacher has \( 3\) grade \(4\) gym classes with \(21, 35\) and \(28\) students in them. The teacher wants to order equipment that equal-sized groups can use in each class. What is the largest group size that will work for all \(3\) classes?
Solution:
You will need to find the GCD of all \(3\) classes.
Firstly, you will find the GCD of \(21\) and \(35.\)
The positive divisors of \(21\) are \(1, 3, 7,\) and \(21\).
The positive divisors of \(35\) are \(1, 5, 7,\) and \(35\).
The GCD of \(21\) and \(35\) is \(7.\)
Since \(7 \mid 28\) you will now find the GCD of \(7\) and \(28\), which turns out to be 7.
Therefore the GCD of \( 21, 35 \) and \(28\) is \(7. \)
Thus, the largest number of students in a group for each class will be \(7.\)
Properties:
Let \(a,b,c \in \mathbb{Z}\).
Then:
- \(\gcd(a, a)=|a|, a\ne 0.\)
- \(\gcd(a, b)=\gcd(b, a)\).
- \(\gcd(a,b,c)=\gcd (\gcd(a, b), c)=\gcd (a, \gcd(b, c))\).
- \(\gcd(a, 0)=a\).
- \(\gcd(0, 0)\) is undefined.
Now, let's explore an algorithm for determining the GCD. The Euclidean Algorithm, developed by the renowned Greek mathematician Euclid, is a highly effective method for computing the GCD of two integers.
If \(a,b \in \mathbb{Z} \setminus \{0\}\), then by using division algorithm iteratively, we obtain
\begin{eqnarray*}a &=bq_0+r_0 \\ b &=r_0 q_1+r_1 \\ r_0 &=r_1q_2+r_2\\ \vdots \\ r_{n-2} &=r_{n-1}q_{n}+r_n \\ r_{n}&=r_nq_{n+1}+0 \\ \end{eqnarray*}
Notice that, the last non-zero remainder is \(r_{n}\), such an \(r_n\) exists, since \(|b|>|r_0|>|r_1| \cdots >|r_n|.\) The \(r_n=\gcd(a,b)\).
Find \(\gcd(2420, 230)\).
Note: Work from right to left to follow the steps shown in the image below.
Hence, \(\gcd(2420,230) =10\).
BEZOUT'S IDENTITY
For integers a and b, let d be the greatest common divisor, d = GCD (a, b). Then there exists integers x and y such that ax+by=d. Any integer that is of the form ax+by, is a multiple of d.
Note
This condition will be a necessary and sufficient case of \(d=1\). We will prove this result in the section Relatively Prime numbers.
Write gcd as a linear combination. \(\gcd(2071,31)=2071x+31y\), with \(x,y \in \mathbb{Z}\).
Solution
Steps are listed (a,b,c,d) for ease of reference to Bezout’s algorithm
a) \(2071=31(66)+25\)
b) \(31=25(1)+6\)
c) \(25=6(4) +1\)
d) \(6=1(6)+0\). The process stops when the remainder is zero. Thus, \(\gcd =1\).
Bezout’s Algorithm
-
\(25=2071+31(-66)\) from a) above.
-
\(6=31+25(-1)\) from b) above.
-
\(1=25 +6(-4)\) from c) above.
\(1=25+6(-4)\) from 3) above.
\(=25+(31+25(-1))(-4)=25(5)+31(-4)\) using 2) above.
\(=(2071 +31(-66))(5)+31(-4)\) using 1) above
Write gcd as a linear combination. \(\gcd(3915,825)=3915x+825y\), with \(x,y \in \mathbb{Z}\).
Solution
From the calculation below, \(\gcd(3915,825)=15.\)
We will use the following tabular method:
Thus, \(\gcd(3915,825)=3915(-4)+825(20)\).
Let \(a,b \in \mathbb{Z}\backslash \{0\}\). Prove or disprove: \(d=ax+by\) for some \(x,y \in \mathbb{Z}\) then \(\gcd(a,b)=d\).
Counterexample:
Let \(d=6, \ a=2071,\) and \(b=31\).
Consider \(6=2071(-1)+31(67)\).
Further consider that \(1=2017(5)+31(-334)\).
Since \(1<6\) and 1 is the lowest possible \(\gcd(a,b)\).
Prove or disprove: If \(1=ax+by\) then \(\gcd(a,b)=1\).
Proof:
Let \(a,b \in \mathbb{Z} \backslash \{0\}\) s.t. \(1=ax+by\) with \(x,y \in \mathbb{Z}.\)
Suppose \(d=\gcd(a,b)\). We will show that \(d=1\).
Since \(d=\gcd(a,b), \;\; d|a\) and \(d|b\).
Since \(d|a, a=md, \; m \in \mathbb{Z}\).
Since \(d|b, b=nd, \; n \in \mathbb{Z}.\)
Now, \(ax+by=(md)x+(nd)y\)
\(=d(mx+ny\).
Since \(mx, ny \in \mathbb{Z}, mx+ny \in \mathbb{Z}\).
Now \(1=ax+by=d(mx+ny)\).
Therefore \(d|1\).
Thus, \(d= \pm 1\), but since \(d\ge 0, d=1\).
Relatively prime
Two integers \(a\) and \(b\) are said to be relatively prime if \(\gcd(a,b)=1\).
Show that \(\gcd(n,n+1)=1, \ \forall n \in \mathbb{Z}\). That is, show that any two consecutive integers are relatively prime.
Since \(n(-1)+(n+1)(1)=1\), \(\gcd(n,n+1)=1\).
Find two integers \(x\) and \(y\) such that \(\gcd(-4357,3754)= -4357(x)+3754(y)\).
First use Euclidean Algorithm
\(-4357=3754(-2)+3151\) Note: Remainder must be greater than or equal to zero.
\begin{eqnarray*}3754 & =3151(1)+603\\3151&= 603(5)+136\\603 & =136(4)+59\\136 & =59(2)+18\\59 & =18(3)+5\\18 & =5(3)+3\\5 & =3(1)+2\\3 & =2(1)+1\\2& =1(2)+0\\\end{eqnarray*}
Therefore \(\gcd(-4357,3754)=1.\)
Then use Bezout’s Algorithm.
Thus \(\gcd(-4357,3754)=-4357(1463)+3754(1698)=1.\)
For \(n \in \mathbb{N}\), the Euler's totient function \(\phi(n)\) is defined to be the number of positive integers less than \(n\) that are relatively prime to \(n\).
Euler's totient function has numerous applications in number theory, cryptography, and other branches of mathematics. It plays a vital role in RSA encryption, where it is used to compute the encryption and decryption keys.
Determine the value \(\phi(n)\) for each integer \(n \le 30\). For \(n \in \mathbb{N}\), \(\phi(n)\) is defined to be the number of positive integers less than or equal to \(n\) that are relatively prime to \(n\).
Number of \(n \in \mathbb{N}\), Relatively Prime to \(n\) |
||
\(n\) |
\(\phi (n)\) |
Set of \(n \in \mathbb{N}\) that are relatively Prime to \(n\). |
1 |
1 |
{1} |
2 |
1 |
{1} |
3 |
2 |
{1,2} |
4 |
2 |
{1,3} |
5 |
4 |
{1,2,3,4} |
6 |
2 |
{1,5} |
7 |
6 |
{1,2,3,4,5,6} |
8 |
4 |
{1,3,5,7} |
9 |
6 |
{1,2,4,5,7,8} |
10 |
4 |
{1,3,7,9} |
11 |
10 |
{1,2,3, … ,8,9,10} |
12 |
4 |
{1,5,7,11} |
13 |
12 |
{1,2,3, … ,10,11,12} |
14 |
6 |
{1,3,5,9,11,13} |
15 |
8 |
{1,2,4,7,8,11,13,14} |
16 |
8 |
{1,3,5,7,9,11,13,15} |
17 |
16 |
{1,2,3, … ,14,15,16} |
18 |
6 |
{1,5,7,11,13,17} |
19 |
18 |
{1,2,3, … ,16,17,18} |
20 |
8 |
{1,3,7,9,11,13,17,19} |
21 |
12 |
{1,2,4,5,8,10,11,13,16,17,19,20} |
22 |
10 |
{1,3,5,7,9,13,15,17,19,21} |
23 |
22 |
{1,2,3, … ,20,21,22} |
24 |
8 |
{1,5,7,11,13,17,19,23} |
25 |
20 |
{1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24} |
26 |
12 |
{1,3,5,7,9,11,15,17,19,21,23,25} |
27 |
18 |
{1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26} |
28 |
12 |
{1,3,5,9,11,13,15,17,19,23,25,27} |
29 |
28 |
{1,2,3, … ,26,27,28} |
30 |
8 |
{1,7,11,13,17,19,23,29} |
Least Common Multiples
Definition: Least Common Multiples
Let \(a\) and \(b\) be integers. Then any integer that is a multiple of both \(a\) and \(b\) is called a common multiple of \(a\) and \(b\). The least common multiple of integers a and b, denoted by \(lcm(a,b)\), is the smallest positive common multiple of \(a\) and \(b\).
Example \(\PageIndex{13}\):
Find
1. \(lcm(5,10)\)
2. \(lcm(-6,18)\)
3. \(lcm(0,5)\)
Solution
1. \(10\), 2. \(18\) 3. undefined.
Finding LCM using GCD
The least common multiple of integers a and b, also known as the LCM, is the smallest number divisible by both integers a and b. You can determine the LCM by dividing the absolute value of the product of a and b by the GCD of \(a\) and \(b\).
That is
\[ lcm(a,b)= \displaystyle \frac{|ab|}{\gcd(a,b)}\]
Example \(\PageIndex{14}\):
What is the LCM of \(24\) and \( 35\)?
Solution:
We must first determine the GCD of \(24\) and \(35\).
Find the divisors of \(24\) and \(35.\)
\(24: 1, 2, 3, 4, 8, 12, 24\)
\(35: 1, 5, 7, 35\)
Therefore the GCD of \(24\) and \(35\) is \(1.\)
Now that we have determined the GCD, we can continue to determine the least common multiple.
\(\frac{(24)(35)}{1}= 840.\)
Hence \(lcm(24,35)=840.\)
Properties:
Let \(a,b,c \in \mathbb{Z}\).
Then:
- \(lcm(a, a)=a.\)
- \(lcm(a, b)=lcm(b, a)\).
- \(lcm(a,b,c)=lcm (lcm(a, b), c)=lcm(a, lcm(b, c))\).
- \(lcm(a,0)=\) undefined.