Use the Euclidean algorithm to find the greatest common divisor of 259 and 581.

Hence, or otherwise, find the general solution to the diophantine equation 259x + 581y = 7 .

$581 = 2 \times 259 + 63$     M1A1

$259 = 4 \times 63 + 7$     A1

$63 = 9 \times 7$

the GCD is therefore 7     A1

[4 marks]

consider

$7 = 259 - 4 \times 63$     M1

$= 259 - 4 \times (581 - 2 \times 259)$     A1

$= 259 \times 9 + 581 \times ( - 4)$     A1

the general solution is therefore

$x = 9 + 83n;{\text{ }}y = - 4 - 37n{\text{ where }}n \in \mathbb{Z}$     M1A1

Notes: Accept solutions laid out in tabular form. Dividing the diophantine equation by 7 is an equally valid method.

[5 marks]