The Euclidean algorithm finds gcd(a,b) by repeated division: gcd(a,b)=gcd(b,r)
Lesson 2 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
find an HCF quickly with the Euclidean algorithm, even for large numbers;
run the algorithm backwards to find x and y with ax+by=gcd(a,b);
prove Bezout's identity and Euclid's lemma, and decide when ax+by=c has integer solutions.
A faster road
To find gcd(1071,462) by factorising, you must break both numbers into primes. Euclid found a faster road about two thousand three hundred years ago. It uses only division.
The key is rule 1 of the last lesson. If a=bq+r, then gcd(a,b)=gcd(b,r). The new pair is smaller. Repeat until the remainder is 0.
1071=462×2+147
462=147×3+21
147=21×7+0
So gcd(1071,462)=gcd(462,147)=gcd(147,21)=gcd(21,0)=21. The HCF is the last non-zero remainder.
Why does it stop? The remainders are whole numbers that fall at every step, so they reach 0 after finitely many steps. It is fast, too. Gabriel Lamé proved in 1844 that the number of divisions is at most five times the number of digits of the smaller number. The slowest pairs are consecutive Fibonacci numbers.
A rectangle 1071 units long and 462 units high, cut into squares. Two large squares of side 462 fill the left part, leaving a strip 147 wide. That strip holds three squares of side 147, leaving a strip 21 wide, which is filled exactly by seven squares of side 21. The labels show 1071 = 2 times 462 + 147, 462 = 3 times 147 + 21 and 147 = 7 times 21, so the smallest square, of side 21, is the HCF.
Running it backwards
Start from the last line with a non-zero remainder and work up.
From the second line: 21=462−3×147.
From the first line: 147=1071−2×462. Put it in.
21=462−3(1071−2×462)=7×462−3×1071.
So 21=1071×(−3)+462×7. The HCF is a combination of the two numbers.
Bezout's identity
Theorem (Bezout's identity). For integers a and b, not both 0, there are integers x and y with
ax+by=gcd(a,b).
Moreover, gcd(a,b) is the smallest positive number of the form ax+by.
Proof. Let S be the set of positive numbers of the form ax+by. It is not empty, since a2+b2>0 is in it. Let d=ax0+by0 be its smallest element.
d divides a. Divide: a=dq+r with 0≤r<d. Then r=a−dq=a(1−qx0)+b(−qy0) is a combination of a and b. If r>0, it would be in S and smaller than d. So r=0 and d∣a. In the same way d∣b.
d is the largest common divisor. Any common divisor c of a and b divides ax0+by0=d, so c≤d.
So d=gcd(a,b). Proof complete.
The name is spelt Bezout or Bézout; both are used. Some books call it the Euclidean property or the linear combination theorem.
Euclid's lemma at last
Euclid's lemma. If a prime p divides ab, then p∣a or p∣b.
Proof. Suppose p∤a. The only positive divisors of p are 1 and p, so gcd(p,a)=1. By Bezout, px+ay=1 for some integers x and y. Multiply by b: pbx+aby=b. Now p divides pbx, and p divides ab, so p divides the sum b. Proof complete.
This closes the gap in course 1: the fundamental theorem of arithmetic is now fully proved.
Which equations ax+by=c can be solved?
Every combination ax+by is a multiple of gcd(a,b). And every multiple of gcd(a,b) is a combination: multiply Bezout's x and y by the right number. So
ax+by=c has integer solutions⟺gcd(a,b)∣c.
For example, 6x+15y=7 has no integer solutions, because 3∤7. Finding all the solutions is part of the next chapter, on Diophantine equations.
Two famous HCFs
The same subtracting idea gives two neat facts. You can prove both with the algorithm.
gcd(2m−1,2n−1)=2gcd(m,n)−1. The exponents follow the Euclidean algorithm themselves.
For the Fibonacci numbers F1=F2=1, Fk+2=Fk+1+Fk, we have gcd(Fm,Fn)=Fgcd(m,n). Two neighbours Fk and Fk+1 are always coprime.
Practise with new numbers
Try it in Python
The program prints each division of the Euclidean algorithm. Then the extended algorithm finds x and y for Bezout's identity.
Common mistakes
Stopping one line early. The HCF is the last non-zero remainder, not the last quotient.
Thinking x and y are unique.21=1071×(−3)+462×7=1071×19+462×(−44). Adding 462/21=22 to x and taking 1071/21=51 from y gives another pair.
Expecting x and y to be positive. One of them is usually negative.
Using Euclid's lemma for a composite number. It needs a prime, or at least gcd(p,a)=1.
Remember these
gcd(a,b)=gcd(b,r), where a=bq+r. The HCF is the last non-zero remainder.
Bezout: ax+by=gcd(a,b) for some integers x, y, and the HCF is the smallest positive combination.
gcd(a,b)=1 exactly when ax+by=1 has a solution.
ax+by=c has integer solutions exactly when gcd(a,b)∣c.
Euclid's lemma follows from Bezout.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Find gcd(2023,1547) with the Euclidean algorithm.
Find integers x and y with 35x+22y=1.
Can 12x+30y=9 be solved in integers?
Prove that gcd(a,b)=1 and gcd(a,c)=1 together give gcd(a,bc)=1.
What is gcd(212−1,218−1)?
References
David M. Burton, Elementary Number Theory, Chapter 2, sections 2.3 and 2.4 on Bezout's identity and the Euclidean algorithm.
Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers, Chapter 1, section 1.2 on primes and Euclid's lemma.
Enroll free in Common Factors, the Euclidean Algorithm and Divisors
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.