Practise › Questions › The Euclidean algorithm and Bezout's identity
The Euclidean algorithm and Bezout's identity questions
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.
7 original questions · 28 marks · the the euclidean algorithm and bezout's identity notes · Further Pure 2
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Use the Euclidean algorithm to find the highest common factor of 1001 and 357.
Worked answer
1001 = 2 × 357 + 287; 357 = 1 × 287 + 70; 287 = 4 × 70 + 7; 70 = 10 × 7 + 0. The last non-zero remainder is 7. M1 for the repeated division, A1 for a correct chain of divisions, A1 for 7. No factorisation of either number was needed.The Euclidean algorithm applied to 1001 and 357 gives 1001 = 2 × 357 + 287, 357 = 1 × 287 + 70, 287 = 4 × 70 + 7 and 70 = 10 × 7. Express the highest common factor in the form 1001x + 357y.
Worked answer
The highest common factor is the last non-zero remainder, 7. Work back up the divisions, one line at a time.
From the third line, 7 = 287 − 4 × 70.
Substituting 70 = 357 − 287: 7 = 287 − 4(357 − 287) = 5 × 287 − 4 × 357.
Substituting 287 = 1001 − 2 × 357: 7 = 5(1001 − 2 × 357) − 4 × 357 = 5 × 1001 − 14 × 357.
So x = 5 and y = −14. Check: 5005 − 4998 = 7. M1 for working back through the divisions, A1 for a correct intermediate line, A1 for x = 5 and y = −14. Keep 287 and 70 as symbols until the end; multiplying them out early loses the structure and the method mark with it.Find the highest common factor of 2024 and 748, and write it in Bezout form.
Worked answer
2024 = 2 × 748 + 528; 748 = 1 × 528 + 220; 528 = 2 × 220 + 88; 220 = 2 × 88 + 44; 88 = 2 × 44 + 0, so the factor is 44. Unwinding: 44 = 220 − 2 × 88 = 5 × 220 − 2 × 528 = 5 × 748 − 7 × 528 = 19 × 748 − 7 × 2024. Check: 14212 − 14168 = 44. M1 for the divisions, A1 for 44, M1 for the back substitution, A1 for the Bezout form.Show that 391 and 299 are not coprime, and state their highest common factor.
Worked answer
391 = 1 × 299 + 92; 299 = 3 × 92 + 23; 92 = 4 × 23 + 0, so the highest common factor is 23 and the numbers are not coprime. M1 for the algorithm, A1 for 23, B1 for the statement that they share a factor. (Indeed 391 = 17 × 23 and 299 = 13 × 23, though the algorithm found the factor without looking for it.)Use Bezout's identity to find the multiplicative inverse of 11 modulo 26.
Worked answer
26 = 2 × 11 + 4; 11 = 2 × 4 + 3; 4 = 1 × 3 + 1, so the numbers are coprime. Unwinding: 1 = 4 − 3 = 3 × 4 − 11 = 3 × 26 − 7 × 11. Reducing modulo 26 gives −7 × 11 ≡ 1, so the inverse is −7 ≡ 19. M1 for the algorithm, A1 for the Bezout identity, M1 for reducing modulo 26, A1 for 19. Checking: 11 × 19 = 209 = 8 × 26 + 1.Find all integer solutions of 12x + 45y = 6.
Worked answer
The highest common factor of 12 and 45 is 3, which divides 6, so solutions exist. Had it not divided 6 there would be none.
Euclid gives 45 = 3 × 12 + 9 and 12 = 1 × 9 + 3, so 3 = 12 − 9 = 12 − (45 − 3 × 12) = 4 × 12 − 45.
Doubling: 6 = 8 × 12 − 2 × 45, giving the particular solution x = 8, y = −2.
Adding 45/3 = 15 to x and subtracting 12/3 = 4 from y leaves the left-hand side unchanged, so the general solution is x = 8 + 15t, y = −2 − 4t for integer t. B1 for checking that 3 divides 6, M1 for a particular solution, A1 for x = 8 and y = −2, A1 for the general form. Dividing by the highest common factor before forming those steps is essential; using 45 and 12 themselves gives only some of the solutions.Use the Euclidean algorithm to show that 84 and 55 are coprime, and find integers x and y such that 84x + 55y = 1. Hence write down the multiplicative inverse of 55 modulo 84, and give the general solution of 84x + 55y = 1.
Worked answer
The algorithm.
84 = 1 × 55 + 29
55 = 1 × 29 + 26
29 = 1 × 26 + 3
26 = 8 × 3 + 2
3 = 1 × 2 + 1
2 = 2 × 1 + 0
The last non-zero remainder is 1, so the two numbers are coprime.
Back substitution. Take the lines in reverse, replacing one remainder at a time and never multiplying out:
1 = 3 − 2
= 3 − (26 − 8 × 3) = 9 × 3 − 26
= 9(29 − 26) − 26 = 9 × 29 − 10 × 26
= 9 × 29 − 10(55 − 29) = 19 × 29 − 10 × 55
= 19(84 − 55) − 10 × 55 = 19 × 84 − 29 × 55.
So x = 19 and y = −29. Check: 1596 − 1595 = 1.
The inverse. Reducing modulo 84 kills the 84 term, leaving −29 × 55 ≡ 1, so the inverse of 55 is −29 ≡ 55 (mod 84). Check: 55² = 3025 = 36 × 84 + 1, so 55 is its own inverse.
General solution. Adding 55 to x and subtracting 84 from y changes nothing, since 84 × 55 − 55 × 84 = 0. So x = 19 + 55t, y = −29 − 84t for integer t.
M1 A1 for the algorithm, A1 for the coprimality statement, M1 A1 for the back substitution, B1 for the inverse, A1 for the general solution.
Six divisions is long for a pair this size. That is what consecutive Fibonacci-like numbers do to the algorithm, and it is exactly when a slip in one quotient quietly wrecks every line below it. Check the identity at the end.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise the euclidean algorithm and bezout's identity one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.