Questions on the Euclidean algorithm and Bézout's identity

Question 1

Use the Euclidean algorithm to find the highest common factor of 1001 and 357.

Accepted 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.

Question 2

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.

Accepted 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 hides the structure the back-substitution relies on.

Question 3

State the division theorem for an integer a and a positive integer b.

Accepted Answer

There are integers q and r with a = bq + r and 0 ≤ r < b. B1 for the equation with the range of r. Those two integers are unique: q is fixed as the largest integer with bq ≤ a, and r is then a − bq. B1 for uniqueness. The restriction on r is what makes the statement say something, since without it a = bq + r holds for every q. It is also what makes the Euclidean algorithm stop, because the remainders form a strictly decreasing sequence of non-negative integers.

Question 4

Write 1000 in base 7.

Accepted Answer

Divide by 7 repeatedly, keeping the remainder at each step. 1000 = 7 × 142 + 6; 142 = 7 × 20 + 2; 20 = 7 × 2 + 6; 2 = 7 × 0 + 2. M1 for the repeated division, A1 for the four remainders. Reading the remainders upwards, from the last division to the first, gives 2626₇. A1. Checking, 2 × 343 + 6 × 49 + 2 × 7 + 6 = 686 + 294 + 14 + 6 = 1000. The remainders come out in order of increasing place value, so writing them down in the order they appeared would reverse the numeral.

Question 5

Find the highest common factor of 2024 and 748, and write it in Bézout form.

Accepted 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 Bézout form.

Question 6

Show that 391 and 299 are not coprime, and state their highest common factor.

Accepted 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.)

Question 7

Use Bézout's identity to find the multiplicative inverse of 11 modulo 26.

Accepted 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 Bézout identity, M1 for reducing modulo 26, A1 for 19. Checking: 11 × 19 = 209 = 8 × 26 + 1.

Question 8

Find all integer solutions of 12x + 45y = 6.

Accepted 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.

Question 9

Find the highest common factor of 4032 and 1155, and express it in the form 4032x + 1155y.

Accepted Answer

4032 = 3 × 1155 + 567; 1155 = 2 × 567 + 21; 567 = 27 × 21 + 0. The last non-zero remainder is 21. M1 for the repeated division, A1 for 21.
Unwinding, and keeping the remainders as symbols: 21 = 1155 − 2 × 567 = 1155 − 2(4032 − 3 × 1155) = 7 × 1155 − 2 × 4032, so x = −2 and y = 7. M1 for the back substitution, A1 for the Bézout form. Checking, 8085 − 8064 = 21. Multiplying 567 out to a number in the first line would leave nothing to substitute into at the second.

Question 10

Explain why any common divisor of two integers a and b also divides ma + nb for all integers m and n, and use that fact to show that 5n + 3 and 3n + 2 are coprime for every integer n.

Accepted Answer

If d divides a and d divides b then a = dk and b = dl for some integers k and l, so ma + nb = d(mk + nl), which is d times an integer. Hence d divides ma + nb. M1 for writing a and b as multiples of d, A1 for factorising d out of the combination.
Now let d be a common divisor of 5n + 3 and 3n + 2. Choose the multipliers that cancel n: 3(5n + 3) − 5(3n + 2) = 15n + 9 − 15n − 10 = −1. M1 for choosing 3 and 5, the swapped coefficients of n. By the first part d divides −1, so d = 1 and the two numbers are coprime whatever n is. A1 for the conclusion. The pair is coprime for every n at once, which no amount of testing particular values of n could establish.

Question 11

The numeral 123 written in base n stands for 83 in base ten. Find n, and then write 83 in base 5.

Accepted Answer

The digits 1, 2 and 3 stand for 1 × n² + 2 × n + 3, so n² + 2n + 3 = 83, that is n² + 2n − 80 = 0. M1 for the place-value equation. Factorising, (n + 10)(n − 8) = 0, and a base is positive, so n = 8. A1. Every digit used is below 8, as it must be.
For the second part, divide 83 by 5 repeatedly: 83 = 5 × 16 + 3; 16 = 5 × 3 + 1; 3 = 5 × 0 + 3. M1 for the repeated division. Reading the remainders upwards gives 313₅, and 3 × 25 + 1 × 5 + 3 = 83 checks it. A1. The negative root −10 is rejected on the meaning of a base, not on the algebra, and a numeral containing the digit 3 could not have been written in any base below 4 anyway.

Question 12

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.

Accepted 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.

Question 13

Given Bézout's identity, prove Euclid's lemma: if a prime p divides ab then p divides a or p divides b. Explain why the same statement fails when p is replaced by a composite number.

Accepted Answer

Suppose p does not divide a. The only positive divisors of p are 1 and p, and p does not divide a, so the highest common factor of p and a is 1. M1 for that step. Bézout then gives integers x and y with px + ay = 1. A1.
Multiply through by b: pbx + aby = b. M1. Now p divides pbx, and p divides ab by hypothesis, so p divides aby. Hence p divides their sum, which is b. A1 for the conclusion. So p divides a or p divides b, as claimed.
For a composite modulus the argument breaks at the first step, because a composite number can share a factor with a without dividing it. Concretely, 6 divides 2 × 3 = 6, yet 6 divides neither 2 nor 3. B1 for the counterexample.

Question 14

State the fundamental theorem of arithmetic, and explain what its uniqueness claim rests on. Show that uniqueness can fail in a set of numbers closed under multiplication by considering the positive integers that leave remainder 1 on division by 3.

Accepted Answer

Every integer greater than 1 is a product of primes. B1 for existence. That product is unique apart from the order in which the factors are written. B1 for uniqueness up to order.
The existence half needs nothing more than repeated splitting of a composite factor, which stops because the factors strictly decrease. Uniqueness rests on Euclid's lemma, that a prime dividing a product divides one of the factors: without it, two different prime factorisations of the same number could not be matched up term by term. M1 for naming Euclid's lemma. That lemma in turn rests on Bézout's identity, which rests on the Euclidean algorithm, which rests on the division theorem. A1 for the chain.
Now take the set 1, 4, 7, 10, 13, … of positive integers congruent to 1 modulo 3. A product of two such numbers is again one, so the set is closed under multiplication and factorisation inside it makes sense. M1 for the closure. Inside that set, 4, 10 and 25 cannot be split, because their only factorisations as integers are 2 × 2, 2 × 5 and 5 × 5, and neither 2 nor 5 belongs to the set. Yet 100 = 4 × 25 and 100 = 10 × 10, two genuinely different factorisations into unsplittable members. A1 for the two factorisations of 100.

Question 15

Show that the equation 91x + 133y = 21 has integer solutions, find them all, and determine whether any of them has both x and y positive.

Accepted Answer

Run the Euclidean algorithm on the two coefficients: 133 = 1 × 91 + 42; 91 = 2 × 42 + 7; 42 = 6 × 7 + 0. The highest common factor is 7, and 7 divides 21, so solutions do exist. M1 for the algorithm, A1 for 7 dividing 21.
Back-substituting, 7 = 91 − 2 × 42 = 91 − 2(133 − 91) = 3 × 91 − 2 × 133. Multiplying by 3, since 21 = 3 × 7, gives 21 = 9 × 91 − 6 × 133, so x = 9 and y = −6 is one solution. M1 for the back substitution, A1 for the particular solution.
Adding 133/7 = 19 to x and subtracting 91/7 = 13 from y leaves the left-hand side unchanged, so the general solution is x = 9 + 19t, y = −6 − 13t for integer t. A1.
For both to be positive, 9 + 19t > 0 needs t ≥ 0, while −6 − 13t > 0 needs t ≤ −1. No integer t satisfies both, so no solution has x and y both positive. B1 for that conclusion with the two inequalities.
The steps 19 and 13 come from dividing the coefficients by 7 first; using 133 and 91 themselves would list only one solution in every seven.