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