(a)     Use the Euclidean algorithm to find gcd(\(12\,306\), 2976) .

(b)     Hence give the general solution to the diophantine equation \(12\,306\)x + 2976y = 996 .

(a)     \(12\,306 = 4 \times 2976 + 402\)     M1

\(2976 = 7 \times 402 + 162\)     M1

\(402 = 2 \times 162 + 78\)     A1

\(162 = 2 \times 78 + 6\)     A1

\(78 = 13 \times 6\)

therefore gcd is 6     R1 

[5 marks]

(b)     \(6|996\) means there is a solution

\(6 = 162 - 2(78)\)     (M1)(A1)

\( = 162 - 2\left( {402 - 2(162)} \right)\)

\( = 5(162) - 2(402)\)     (A1)

\( = 5(2976) - 7(402)} \right) - 2(402)\)

\( = 5(2976) - 37(402)\)     (A1)

\( = 5(2976) - 37\left( {12\,306 - 4(2976)} \right)\)

\( = 153(2976) - 37(12\,306)\)     (A1)

\(996 = 25\,398(2976) - 6142(12\,306)\)

\( \Rightarrow {x_0} = - 6142,{\text{ }}{y_0} = 25\,398\)     (A1)

\( \Rightarrow x = - 6142 + \left( {\frac{{2976}}{6}} \right)t = - 6142 + 496t\)

\( \Rightarrow y = 25\,398 - \left( {\frac{{12\,306}}{6}} \right)t = 25\,398 - 2051t\)     M1A1A1

[9 marks]

Total [14 marks]

Part (a) of this question was the most accessible on the paper and was completed correctly by the majority of candidates. Most candidates were able to start part (b), but a number made errors on the way and quite a number failed to give the general solution.