Using the Euclidean algorithm, show that $\gcd (99,{\text{ }}332) = 1$.

(i)     Find the general solution to the diophantine equation $332x - 99y = 1$.

(ii)     Hence, or otherwise, find the smallest positive integer satisfying the congruence $17z \equiv 1(\bmod 57)$.

using the Euclidean Algorithm,

$332 = 3 \times 99 + 35{\text{ }}$     M1

$99 = 2 \times 35 + 29$     A1

$35 = 1 \times 29 + 6$

$29 = 4 \times 6 + 5$     A1

$6 = 1 \times 5 + 1$     A1

hence 332 and 99 have a gcd of 1     AG

Note: For both (a) and (b) accept layout in tabular form, especially the brackets method of keeping track of the linear combinations as the method proceeds.

[4 marks]

(i)     working backwards,     (M1)

$6 - 5 = 1$

$6 - (29 - 4 \times 6) = 1{\text{ or }}5 \times 6 - 29 = 1$     A1

$5 \times (35-29)-29 = 1{\text{ or }}5 \times 35-6 \times 29 = 1$     A1

$5 \times 35-6 \times (99-2 \times 35) = 1{\text{ or }}17 \times 35-6 \times 99 = 1$

$17 \times (332-3 \times 99)-6 \times 99 = 1{\text{ or }}17 \times 332-57 \times 99 = 1$     A1

a solution to the Diophantine equation is therefore

$x = 17,{\text{ }}y = 57$     (A1)

the general solution is

$x = 17 + 99N,{\text{ }}y = 57 + 332N$     A1A1

Note: If part (a) is wrong it is inappropriate to give FT in (b) as the numbers will contradict, however the M1 can be given.

(ii)     it follows from previous work that

$17 \times 332 = 1 + 99 \times 57$     (M1)

$\equiv 1(\bmod 57)$     (A1)

z = 332 is a solution to the given congruence     (A1)

the general solution is 332 + 57N so the smallest solution is 47     A1

[11 marks]

Part (a) was well answered and (b) fairly well answered. There were problems with negative signs due to the fact that there was a negative in the question, so candidates had to think a little, rather than just remembering formulae by rote. The lay-out of the algorithm that keeps track of the linear combinations of the first 2 variables is recommended to teachers.

Part (a) was well answered and (b) fairly well answered. There were problems with negative signs due to the fact that there was a negative in the question, so candidates had to think a little, rather than just remembering formulae by rote. The lay-out of the algorithm that keeps track of the linear combinations of the first 2 variables is recommended to teachers.