The Central Idea
Suppose \(a>b>0\). By the division algorithm, we can write
\[ a=bq+r, \qquad 0\le rThis lets us replace the pair \((a,b)\) with the smaller pair \((b,r)\) without changing the greatest common divisor.
A First Example
Find
\[ \gcd(48,18). \]Divide \(48\) by \(18\):
\[ 48=18(2)+12. \]Replace \((48,18)\) with \((18,12)\):
\[ 18=12(1)+6. \]Replace \((18,12)\) with \((12,6)\):
\[ 12=6(2)+0. \]The last nonzero remainder is \(6\). Therefore,
\[ \boxed{\gcd(48,18)=6}. \]The Repeated-Division Pattern
The algorithm repeatedly performs the same operation:
\[ \text{larger number} = (\text{smaller number})(\text{quotient}) + \text{remainder}. \]Then discard the old larger number and continue with
\[ (\text{smaller number},\text{remainder}). \]The remainders strictly decrease, so the process must eventually reach zero.
Why the GCD Is Preserved
Suppose
\[ a=bq+r. \]Rearranging gives
\[ r=a-bq. \]Any common divisor of \(a\) and \(b\) divides every integer linear combination of \(a\) and \(b\). Therefore any common divisor of \(a\) and \(b\) also divides \(r\).
So every common divisor of \(a\) and \(b\) is also a common divisor of \(b\) and \(r\).
The Reverse Direction
From
\[ a=bq+r, \]any common divisor of \(b\) and \(r\) divides
\[ bq+r=a. \]Therefore every common divisor of \(b\) and \(r\) is also a common divisor of \(a\) and \(b\).
The two pairs have exactly the same common divisors, so
\[ \boxed{\gcd(a,b)=\gcd(b,r)}. \]Why the Last Nonzero Remainder Is the GCD
Eventually the algorithm reaches a step of the form
\[ r_{k-2}=r_{k-1}q_k+0. \]This means
\[ r_{k-1}\mid r_{k-2}. \]Therefore
\[ \gcd(r_{k-2},r_{k-1})=r_{k-1}. \]Since every previous Euclidean step preserved the GCD, the final nonzero remainder is the GCD of the original pair.
Example: \(\gcd(252,105)\)
Begin with
\[ 252=105(2)+42. \]Continue:
\[ 105=42(2)+21. \]Then
\[ 42=21(2)+0. \]The last nonzero remainder is \(21\), so
\[ \boxed{\gcd(252,105)=21}. \]Example: A Longer Chain
Find
\[ \gcd(662,414). \]Apply repeated division:
\[ 662=414(1)+248, \] \[ 414=248(1)+166, \] \[ 248=166(1)+82, \] \[ 166=82(2)+2, \] \[ 82=2(41)+0. \]Therefore,
\[ \boxed{\gcd(662,414)=2}. \]The Quotient Is Not the Main Result
The quotients produced during the Euclidean Algorithm help generate the remainders, but the GCD is determined by the last nonzero remainder.
In
\[ 166=82(2)+2, \]the quotient \(2\) is not the GCD merely because it appears in the calculation. The remainder \(2\) becomes the next divisor and eventually survives as the last nonzero remainder.
The Remainder Must Be Smaller
Each division step uses a remainder satisfying
\[ 0\le rFor example,
\[ 47=13(3)+8 \]is a valid division step because
\[ 0\le8<13. \]Example: \(\gcd(391,299)\)
\[ 391=299(1)+92, \] \[ 299=92(3)+23, \] \[ 92=23(4)+0. \]Therefore,
\[ \boxed{\gcd(391,299)=23}. \]When One Number Divides the Other
The Euclidean Algorithm may stop immediately.
Find
\[ \gcd(84,21). \]Since
\[ 84=21(4)+0, \]the last nonzero remainder is the divisor \(21\). Thus
\[ \boxed{\gcd(84,21)=21}. \]Relatively Prime Numbers
Two positive integers are relatively prime when their GCD is \(1\).
Apply the Euclidean Algorithm to \(35\) and \(22\):
\[ 35=22(1)+13, \] \[ 22=13(1)+9, \] \[ 13=9(1)+4, \] \[ 9=4(2)+1, \] \[ 4=1(4)+0. \]Therefore,
\[ \boxed{\gcd(35,22)=1}. \]Thus \(35\) and \(22\) are relatively prime.
The Algorithm Avoids Full Factorization
Prime factorization can find a GCD, but it requires knowing the complete factorization of both numbers.
The Euclidean Algorithm does not require that information. It uses only division and remainders.
This makes it especially useful when the integers are large or difficult to factor.
Example: A Large Pair
Find
\[ \gcd(12345,6789). \]Apply the algorithm:
\[ 12345=6789(1)+5556, \] \[ 6789=5556(1)+1233, \] \[ 5556=1233(4)+624, \] \[ 1233=624(1)+609, \] \[ 624=609(1)+15, \] \[ 609=15(40)+9, \] \[ 15=9(1)+6, \] \[ 9=6(1)+3, \] \[ 6=3(2)+0. \]Therefore,
\[ \boxed{\gcd(12345,6789)=3}. \]Using the GCD to Find an LCM
Once the GCD is known, the LCM can be found from
\[ \gcd(a,b)\operatorname{lcm}(a,b)=ab. \]Therefore,
\[ \boxed{ \operatorname{lcm}(a,b)= \frac{ab}{\gcd(a,b)} }. \]The Euclidean Algorithm can therefore support efficient LCM calculations as well.
Example: Euclidean Algorithm Followed by LCM
Find the GCD and LCM of \(84\) and \(30\).
\[ 84=30(2)+24, \] \[ 30=24(1)+6, \] \[ 24=6(4)+0. \]Hence
\[ \gcd(84,30)=6. \]Then
\[ \operatorname{lcm}(84,30) = \frac{84\cdot30}{6} = 420. \]Therefore,
\[ \boxed{\gcd(84,30)=6} \qquad\text{and}\qquad \boxed{\operatorname{lcm}(84,30)=420}. \]Back-Substitution
The remainder equations can be read backward to express the GCD as an integer linear combination of the original numbers.
For example, from
\[ 48=18(2)+12 \]we obtain
\[ 12=48-18(2). \]From
\[ 18=12(1)+6 \]we obtain
\[ 6=18-12. \]Example: Expressing the GCD as a Linear Combination
Continue the previous calculation.
Substitute
\[ 12=48-2(18) \]into
\[ 6=18-12. \]Then
\[ 6 = 18-[48-2(18)]. \]Simplify:
\[ 6=3(18)-48. \]Therefore,
\[ \boxed{6=(-1)(48)+3(18)}. \]Bézout Form
The previous example illustrates a broader fact: for integers \(a\) and \(b\), not both zero, there exist integers \(x\) and \(y\) such that
\[ \boxed{\gcd(a,b)=ax+by}. \]An equation of this form is called a Bézout identity.
Reversing the Euclidean Algorithm is one systematic way to find suitable coefficients \(x\) and \(y\).
Why Bézout Form Matters
Writing a GCD as an integer linear combination connects the Euclidean Algorithm to later topics such as:
- linear Diophantine equations;
- modular inverses;
- solving linear congruences;
- introductory cryptography.
For now, the important point is that the Euclidean Algorithm reveals more than the numerical GCD: its equations also encode how that GCD is built from the original integers.
Example: Back-Substitution with More Steps
Find integers \(x\) and \(y\) such that
\[ \gcd(99,78)=99x+78y. \]First run the Euclidean Algorithm:
\[ 99=78(1)+21, \] \[ 78=21(3)+15, \] \[ 21=15(1)+6, \] \[ 15=6(2)+3, \] \[ 6=3(2)+0. \]Thus
\[ \gcd(99,78)=3. \]Continuing the Back-Substitution
Start with
\[ 3=15-2(6). \]Since
\[ 6=21-15, \]substitute:
\[ 3=15-2(21-15)=3(15)-2(21). \]Since
\[ 15=78-3(21), \]we get
\[ 3=3(78)-11(21). \]Finally, because
\[ 21=99-78, \]substitute again:
\[ 3=3(78)-11(99-78). \]Therefore,
\[ \boxed{3=-11(99)+14(78)}. \]Checking a Bézout Identity
Verification is direct.
For
\[ 3=-11(99)+14(78), \]compute
\[ -1089+1092=3. \]The equality holds, confirming the back-substitution.
The Extended Euclidean Algorithm
When the Euclidean Algorithm is used together with systematic back-substitution to find integers \(x\) and \(y\) satisfying
\[ \gcd(a,b)=ax+by, \]the process is often called the Extended Euclidean Algorithm.
Later lessons will use this form when solving modular equations.
Common Error: Stopping at the First Remainder
Consider
\[ 84=30(2)+24. \]The remainder \(24\) is not automatically the GCD. Continue:
\[ 30=24(1)+6, \] \[ 24=6(4)+0. \]Therefore,
\[ \boxed{\gcd(84,30)=6}, \]not \(24\).
Common Error: Reporting Zero as the GCD
The algorithm ends when the remainder becomes zero, but zero is not the answer.
The GCD is the last nonzero remainder.
In
\[ 42=6(7)+0, \]the GCD is \(6\), not \(0\).
Common Error: Using the Wrong Pair Next
After
\[ 73=28(2)+17, \]the next pair is
\[ \boxed{(28,17)}, \]not \((73,17)\).
Each step moves the previous divisor into the dividend position and the previous remainder into the divisor position.
Common Error: Allowing an Oversized Remainder
The remainder must satisfy
\[ 0\le ris not the standard division-algorithm form because \(32>18\).
Instead,
\[ 50=18(2)+14. \]Common Error: Losing Signs in Back-Substitution
Suppose
\[ 6=18-12 \]and
\[ 12=48-2(18). \]Substituting requires parentheses:
\[ 6=18-[48-2(18)]. \]The subtraction changes the sign of every term inside the brackets.
A Reliable Euclidean Algorithm Procedure
- Place the larger positive integer first.
- Divide the larger number by the smaller number.
- Write the division equation \(a=bq+r\) with \(0\le r
- If \(r=0\), stop.
- If \(r\neq0\), replace \((a,b)\) with \((b,r)\).
- Repeat the division.
- Report the last nonzero remainder as the GCD.
A Reliable Back-Substitution Procedure
- Run the Euclidean Algorithm and identify the GCD.
- Take the equation that produced the GCD as a remainder.
- Solve that equation for the GCD.
- Use the preceding remainder equation to replace the next smaller remainder.
- Continue substituting backward.
- Collect coefficients of the original two integers.
- Verify the final linear combination numerically.
Example: Full Euclidean Workflow
Find
\[ \gcd(1071,462). \]Begin:
\[ 1071=462(2)+147. \]Continue:
\[ 462=147(3)+21. \]Then
\[ 147=21(7)+0. \]Therefore,
\[ \boxed{\gcd(1071,462)=21}. \]Checking the Result
A GCD should divide both original integers.
Here,
\[ \frac{1071}{21}=51 \]and
\[ \frac{462}{21}=22. \]Both quotients are integers, so \(21\) is a common divisor.
The Euclidean Algorithm guarantees that it is the greatest common divisor.
Practice 1: Short Algorithm
Find
\[ \gcd(56,24) \]using the Euclidean Algorithm.
Practice 2: Another GCD
Find
\[ \gcd(119,34). \]Practice 3: Relatively Prime?
Determine whether
\[ 89\text{ and }55 \]are relatively prime.
Practice 4: Longer Chain
Find
\[ \gcd(544,119). \]Practice 5: Immediate Termination
Find
\[ \gcd(144,36). \]Practice 6: Find the LCM
Use the Euclidean Algorithm and the product relationship to find
\[ \operatorname{lcm}(54,24). \]Practice 7: Identify the Next Pair
If one Euclidean step is
\[ 155=62(2)+31, \]what pair should be used in the next step?
Practice 8: Explain the Result
A Euclidean Algorithm calculation ends with
\[ 26=13(2)+0. \]What is the GCD, and why is the answer not \(0\)?
Practice 9: Back-Substitution
Given
\[ 35=22(1)+13 \] \[ 22=13(1)+9 \] \[ 13=9(1)+4 \] \[ 9=4(2)+1, \]express \(1\) as an integer linear combination of \(35\) and \(22\).
Practice 10: Identify the Error
A student computes
\[ 91=35(2)+21 \]and concludes that
\[ \gcd(91,35)=21. \]Explain what remains to be done.
Practice Answers
Practice 1
\[ 56=24(2)+8, \] \[ 24=8(3)+0. \]Therefore,
\[ \boxed{\gcd(56,24)=8}. \]Practice 2
\[ 119=34(3)+17, \] \[ 34=17(2)+0. \]Therefore,
\[ \boxed{\gcd(119,34)=17}. \]Practice 3
\[ 89=55(1)+34, \] \[ 55=34(1)+21, \] \[ 34=21(1)+13, \] \[ 21=13(1)+8, \] \[ 13=8(1)+5, \] \[ 8=5(1)+3, \] \[ 5=3(1)+2, \] \[ 3=2(1)+1, \] \[ 2=1(2)+0. \]Thus
\[ \boxed{\gcd(89,55)=1}. \]Therefore the numbers are relatively prime.
Practice 4
\[ 544=119(4)+68, \] \[ 119=68(1)+51, \] \[ 68=51(1)+17, \] \[ 51=17(3)+0. \]Therefore,
\[ \boxed{\gcd(544,119)=17}. \]Practice 5
\[ 144=36(4)+0. \]Therefore,
\[ \boxed{\gcd(144,36)=36}. \]Practice 6
\[ 54=24(2)+6, \] \[ 24=6(4)+0. \]Thus
\[ \gcd(54,24)=6. \]Then
\[ \operatorname{lcm}(54,24) = \frac{54\cdot24}{6} = 216. \]Therefore,
\[ \boxed{\operatorname{lcm}(54,24)=216}. \]Practice 7
The next pair is
\[ \boxed{(62,31)}. \]Practice 8
The remainder \(0\) signals termination. The last nonzero remainder is \(13\), so
\[ \boxed{\gcd=13}. \]Practice 9
Start with
\[ 1=9-2(4). \]Since
\[ 4=13-9, \]substitute:
\[ 1=9-2(13-9)=3(9)-2(13). \]Since
\[ 9=22-13, \]we get
\[ 1=3(22)-5(13). \]Since
\[ 13=35-22, \]substitute:
\[ 1=3(22)-5(35-22). \]Therefore,
\[ \boxed{1=-5(35)+8(22)}. \]Practice 10
The remainder \(21\) is not zero, so the algorithm must continue:
\[ 35=21(1)+14, \] \[ 21=14(1)+7, \] \[ 14=7(2)+0. \]Therefore,
\[ \boxed{\gcd(91,35)=7}. \]What to Remember
- The Euclidean Algorithm finds a GCD using repeated division with remainders.
- The key identity is \(\gcd(a,b)=\gcd(b,r)\) when \(a=bq+r\).
- Each new pair is the previous divisor and previous remainder.
- The remainders decrease until zero appears.
- The GCD is the last nonzero remainder, not the final zero.
- The method avoids complete prime factorization.
- Back-substitution can express the GCD as an integer linear combination of the original numbers.
- The extended form connects directly to later congruence and Diophantine-equation methods.
The essential operating rule is: divide, keep the remainder, replace the pair, and repeat until the remainder is zero.
Where We Go Next
The Euclidean Algorithm finds common divisibility structure without requiring complete factorization. The next lesson, Prime Factorization, returns to the multiplicative building blocks of integers and develops systematic ways to express composite numbers as products of primes.