HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Common Factors, the Euclidean Algorithm and Divisors
  1. 1The highest common factor and the least common multiple
  2. 2The Euclidean algorithm and Bezout's identity
  3. 3Counting and adding the divisors
  1. Mathematics
  2. /Common Factors, the Euclidean Algorithm and Divisors
  3. /The Euclidean algorithm and Bezout's identity

Course 27.2·Lesson 2 of 3

The Euclidean algorithm and Bezout's identity

The Euclidean algorithm finds gcd⁡(a,b)\gcd(a, b)gcd(a,b) by repeated division: gcd⁡(a,b)=gcd⁡(b,r)\gcd(a, b) = \gcd(b, r)gcd(a,b)=gcd(b,r)

Lesson 2 of 3Show all lessonsHide
Common Factors, the Euclidean Algorithm and Divisors
  1. 1The highest common factor and the least common multiple
  2. 2The Euclidean algorithm and Bezout's identity
  3. 3

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 xxx and yyy with ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)ax+by=gcd(a,b);
  • prove Bezout's identity and Euclid's lemma, and decide when ax+by=cax + by = cax+by=c has integer solutions.

A faster road

To find gcd⁡(1071,462)\gcd(1071, 462)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+ra = bq + ra=bq+r, then gcd⁡(a,b)=gcd⁡(b,r)\gcd(a, b) = \gcd(b, r)gcd(a,b)=gcd(b,r). The new pair is smaller. Repeat until the remainder is 000.

1071=462×2+147\displaystyle 1071 = 462 \times 2 + 1471071=462×2+147
462=147×3+21\displaystyle 462 = 147 \times 3 + 21462=147×3+21
147=21×7+0\displaystyle 147 = 21 \times 7 + 0147=21×7+0

So gcd⁡(1071,462)=gcd⁡(462,147)=gcd⁡(147,21)=gcd⁡(21,0)=21\gcd(1071, 462) = \gcd(462, 147) = \gcd(147, 21) = \gcd(21, 0) = 21gcd(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 000 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.

  1. From the second line: 21=462−3×14721 = 462 - 3 \times 14721=462−3×147.
  2. From the first line: 147=1071−2×462147 = 1071 - 2 \times 462147=1071−2×462. Put it in.
  3. 21=462−3(1071−2×462)=7×462−3×107121 = 462 - 3(1071 - 2 \times 462) = 7 \times 462 - 3 \times 107121=462−3(1071−2×462)=7×462−3×1071.

So 21=1071×(−3)+462×721 = 1071 \times (-3) + 462 \times 721=1071×(−3)+462×7. The HCF is a combination of the two numbers.

Bezout's identity

Theorem (Bezout's identity). For integers aaa and bbb, not both 000, there are integers xxx and yyy with

ax+by=gcd⁡(a,b).\displaystyle ax + by = \gcd(a, b).ax+by=gcd(a,b).

Moreover, gcd⁡(a,b)\gcd(a, b)gcd(a,b) is the smallest positive number of the form ax+byax + byax+by.

Proof. Let SSS be the set of positive numbers of the form ax+byax + byax+by. It is not empty, since a2+b2>0a^2 + b^2 > 0a2+b2>0 is in it. Let d=ax0+by0d = ax_0 + by_0d=ax0​+by0​ be its smallest element.

  1. ddd divides aaa. Divide: a=dq+ra = dq + ra=dq+r with 0≤r<d0 \le r < d0≤r<d. Then r=a−dq=a(1−qx0)+b(−qy0)r = a - dq = a(1 - qx_0) + b(-qy_0)r=a−dq=a(1−qx0​)+b(−qy0​) is a combination of aaa and bbb. If r>0r > 0r>0, it would be in SSS and smaller than ddd. So r=0r = 0r=0 and d∣ad \mid ad∣a. In the same way d∣bd \mid bd∣b.
  2. ddd is the largest common divisor. Any common divisor ccc of aaa and bbb divides ax0+by0=dax_0 + by_0 = dax0​+by0​=d, so c≤dc \le dc≤d.

So d=gcd⁡(a,b)d = \gcd(a, b)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 ppp divides ababab, then p∣ap \mid ap∣a or p∣bp \mid bp∣b.

Proof. Suppose p∤ap \nmid ap∤a. The only positive divisors of ppp are 111 and ppp, so gcd⁡(p,a)=1\gcd(p, a) = 1gcd(p,a)=1. By Bezout, px+ay=1px + ay = 1px+ay=1 for some integers xxx and yyy. Multiply by bbb: pbx+aby=bpbx + aby = bpbx+aby=b. Now ppp divides pbxpbxpbx, and ppp divides ababab, so ppp divides the sum bbb. Proof complete.

This closes the gap in course 1: the fundamental theorem of arithmetic is now fully proved.

Which equations ax+by=cax + by = cax+by=c can be solved?

Every combination ax+byax + byax+by is a multiple of gcd⁡(a,b)\gcd(a, b)gcd(a,b). And every multiple of gcd⁡(a,b)\gcd(a, b)gcd(a,b) is a combination: multiply Bezout's xxx and yyy by the right number. So

ax+by=c has integer solutions  ⟺  gcd⁡(a,b)∣c.\displaystyle ax + by = c \text{ has integer solutions} \iff \gcd(a, b) \mid c.ax+by=c has integer solutions⟺gcd(a,b)∣c.

For example, 6x+15y=76x + 15y = 76x+15y=7 has no integer solutions, because 3∤73 \nmid 73∤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\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m, n)} - 1gcd(2m−1,2n−1)=2gcd(m,n)−1. The exponents follow the Euclidean algorithm themselves.
  • For the Fibonacci numbers F1=F2=1F_1 = F_2 = 1F1​=F2​=1, Fk+2=Fk+1+FkF_{k+2} = F_{k+1} + F_kFk+2​=Fk+1​+Fk​, we have gcd⁡(Fm,Fn)=Fgcd⁡(m,n)\gcd(F_m, F_n) = F_{\gcd(m, n)}gcd(Fm​,Fn​)=Fgcd(m,n)​. Two neighbours FkF_kFk​ and Fk+1F_{k+1}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 xxx and yyy for Bezout's identity.

Read it first. Then run it. Is the xxx and yyy it finds the same pair as ours?

1. Change 1071, 462 in both places to two consecutive Fibonacci numbers, such as 233, 144. Count the divisions.

2. Try 6, 15 in extended. What does it give, and why can 6x+15y6x + 15y6x+15y never be 777?

Common mistakes

  • Stopping one line early. The HCF is the last non-zero remainder, not the last quotient.
  • Thinking xxx and yyy are unique. 21=1071×(−3)+462×7=1071×19+462×(−44)21 = 1071 \times (-3) + 462 \times 7 = 1071 \times 19 + 462 \times (-44)21=1071×(−3)+462×7=1071×19+462×(−44). Adding 462/21=22462/21 = 22462/21=22 to xxx and taking 1071/21=511071/21 = 511071/21=51 from yyy gives another pair.
  • Expecting xxx and yyy 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\gcd(p, a) = 1gcd(p,a)=1.

Remember these

  • gcd⁡(a,b)=gcd⁡(b,r)\gcd(a, b) = \gcd(b, r)gcd(a,b)=gcd(b,r), where a=bq+ra = bq + ra=bq+r. The HCF is the last non-zero remainder.
  • Bezout: ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)ax+by=gcd(a,b) for some integers xxx, yyy, and the HCF is the smallest positive combination.
  • gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1 exactly when ax+by=1ax + by = 1ax+by=1 has a solution.
  • ax+by=cax + by = cax+by=c has integer solutions exactly when gcd⁡(a,b)∣c\gcd(a, b) \mid cgcd(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.

  1. Find gcd⁡(2023,1547)\gcd(2023, 1547)gcd(2023,1547) with the Euclidean algorithm.
  1. Find integers xxx and yyy with 35x+22y=135x + 22y = 135x+22y=1.
  1. Can 12x+30y=912x + 30y = 912x+30y=9 be solved in integers?
  1. Prove that gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1 and gcd⁡(a,c)=1\gcd(a, c) = 1gcd(a,c)=1 together give gcd⁡(a,bc)=1\gcd(a, bc) = 1gcd(a,bc)=1.
  1. What is gcd⁡(212−1,218−1)\gcd(2^{12} - 1, 2^{18} - 1)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.
No payment. You can leave at any time.

Problems (4)

A cyclist's wheel has a circumference of 1547 mm and a measuring wheel has a circumference of 560…Hard · High School (11–12) · by StemPy Lab
Numbers of the form 2ᵏ - 1 share factors in a neat way…Advanced · High School (11–12) · by StemPy Lab
A cook has a 7-litre jug, an 11-litre jug, a tap and a large pot…Hard · High School (11–12) · by StemPy Lab
Next: lesson 3Counting and adding the divisors
← Common Factors, the Euclidean Algorithm and Divisors
← The highest common factor and the least common multipleCounting and adding the divisors →

Discussion (0)

Log in to join the discussion.

Loading…

, where
rrr
is the remainder of
aaa
on division by
bbb
. Running it backwards writes the HCF as
ax+byax + byax+by
for some integers
xxx
and
yyy
. This is Bezout's identity, and it proves Euclid's lemma about primes.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Counting and adding the divisors
Prove that the fraction (21n + 4)/(14n + 3) cannot be cancelled for any whole number n…Advanced · High School (11–12) · by StemPy Lab

Python Labs (1)

Euclid and Bezout by machinePython Lab · by StemPy Lab