Maths › Further Pure 2 › The Euclidean algorithm and Bezout's identity

The Euclidean algorithm and Bezout's identity

Divide, keep the remainder, repeat. The last non-zero remainder is the highest common factor, and running the working backwards writes it as a combination of the two numbers you started with.

Year FMEDEXCEL 9FM0 FP2 5.1, 5.2

Builds on The structure of proof and Induction: divisibility.

IN THIS TOPIC

  • State the division theorem and run the Euclidean algorithm to a highest common factor.
  • Back substitute to express the highest common factor as an integer combination.
  • Recognise when two numbers are coprime, and say what that permits.

COMMON MISCONCEPTION

Finding the highest common factor of two large numbers means factorising both into primes.

Divide and keep the remainder

The division theorem says that for integers a and b with b positive, there are unique q and r with a = bq + r and 0 ≤ r < b. The Euclidean algorithm applies it over and over. Replace the pair (a, b) with (b, r) and go again. Remainders strictly decrease, so the process has to stop, and the last non-zero remainder is the highest common factor.

No factorisation happens anywhere, and that is what makes the method practical for numbers far too large to factorise. Finding the prime factorisations first works in principle and fails completely in practice.

The Euclidean algorithm on 1071 and 462: each remainder becomes the next divisor, and the last non-zero one is 21each remainder becomes the next divisor1071 = 2 × 462 + 147462 = 3 × 147 + 21147 = 7 × 21 + 0highest common factor = 21
FIG. 1The Euclidean algorithm on 1071 and 462: three divisions, each feeding its remainder forward, ending at the highest common factor 21.

WORKED EXAMPLE

The algorithm, then backwards

Find the highest common factor of 1071 and 462, and write it as 1071x + 462y for integers x and y.

1071 = 2 × 462 + 147; 462 = 3 × 147 + 21; 147 = 7 × 21 + 0. The last non-zero remainder is 21.

Back substitute: 21 = 462 − 3 × 147, and 147 = 1071 − 2 × 462.

So 21 = 462 − 3(1071 − 2 × 462) = 7 × 462 − 3 × 1071, giving x = −3, y = 7. Checking, −3213 + 3234 = 21.

Bezout's identity

That last step generalises. Bezout's identity says the highest common factor of a and b can always be written as ax + by for some integers x and y, and back substitution through the Euclidean working finds a pair. The pair is not unique. Add a multiple of b to x, subtract the matching multiple of a from y, and you have another.

When the highest common factor is 1 the numbers are coprime, and Bezout reads ax + by = 1. Reduce that modulo b and you get ax ≡ 1, so x is the multiplicative inverse of a modulo b. Modular division rests entirely on this, so the algorithm reappears the moment congruence equations arrive.

Back substitution: the remainders are replaced one at a time until only 1071 and 462 are left21 = 462 − 3 × 147147 = 1071 − 2 × 46221 = 462 − 3(1071 − 2 × 462)21 = 7 × 462 − 3 × 1071substituting upwards, one remainder at a time
FIG. 2Back substitution unwinding: each remainder is replaced by the line above until only 1071 and 462 remain, with integer coefficients.

GUIDED PRACTICE

A smaller pair

Use the Euclidean algorithm to find the highest common factor of 240 and 46, and express it in Bezout form.

Show the working

240 = 5 × 46 + 10; 46 = 4 × 10 + 6; 10 = 1 × 6 + 4; 6 = 1 × 4 + 2; 4 = 2 × 2 + 0, so the highest common factor is 2.

Unwinding: 2 = 6 − 4 = 6 − (10 − 6) = 2 × 6 − 10 = 2(46 − 4 × 10) − 10 = 2 × 46 − 9 × 10, and 10 = 240 − 5 × 46.

So 2 = 2 × 46 − 9(240 − 5 × 46) = 47 × 46 − 9 × 240. Check: 2162 − 2160 = 2.

ASSESSMENT FOCUS

  • Set the divisions out one per line, because the back substitution then reads straight up the page.
  • Stop at the last non-zero remainder, and say which line it came from.
  • In back substitution, replace one remainder at a time and never expand prematurely.
  • Check the Bezout coefficients by substituting back. The arithmetic is quick and the signs are easy to lose.

CHECK YOURSELF

Use the Euclidean algorithm to find the highest common factor of 84 and 30.

Show a hint

Divide, keep the remainder, repeat.

Show the answer

84 = 2 × 30 + 24; 30 = 1 × 24 + 6; 24 = 4 × 6 + 0. The highest common factor is 6.

Euclid: divide, keep the remainder, repeat; the last non-zero remainder is the highest common factor.

Bezout: back substitution writes that factor as ax + by, and when it is 1 the coefficient x inverts a modulo b.

WORKBOOK

Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.

Question workbook

PDF · 32 KB · print edition · white background

Question workbook

PDF · 32 KB · screen edition · navy

Answer book

PDF · 60 KB · fully worked · navy
7 questions on this topicAnswer them one at a time and mark yourself against the worked answer.Practise this topic

Or read them with their worked answers on the the euclidean algorithm and bezout's identity questions page.

CHECK YOUR PROGRESS

Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.

  • State the division theorem and run the Euclidean algorithm to a highest common factor.
  • Back substitute to express the highest common factor as an integer combination.
  • Recognise when two numbers are coprime, and say what that permits.

Open the full revision checklist to see every objective in the course in one place.