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.