4.1: Greatest Common Divisor
- Page ID
- 7533
This page is a draft and is under active development.
\( \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 \(a,b\) not both 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
If \(c \in \mathbb{Z}\), \(c|a\) and \(c|b\) then \(c\le d\). Note: \(d\) is the greatest number that 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 the two integers. 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}\). This section introduces a binary operation on \(\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.
In the next section, we will learn an algorithm to calculate GCD.
Practical Uses:
There are many real-world applications for learning the greatest common divisor (gcd).
- Fractions
- Algebra
- Foundational word problem skills
- Ratios
- Recipes
- Group arrangements