Use the Euclidean algorithm to find the greatest common divisor of the numbers 56 and 315.

(i)     Find the general solution to the diophantine equation $56x + 315y = 21$.

(ii)     Hence or otherwise find the smallest positive solution to the congruence $315x \equiv 21$ (modulo 56) .

$315 = 5 \times 56 + 35$     M1

$56 = 1 \times 35 + 21$

$35 = 1 \times 21 + 14$     A1

$21 = 1 \times 14 + 7$

$14 = 2 \times 7$     A1

therefore gcd = 7     A1

[4 marks]

(i)     $7 = 21 - 14$     M1

$= 21 - (35 - 21)$

$= 2 \times 21 - 35$     (A1)

$= 2 \times (56 - 35) - 35$

$= 2 \times 56 - 3 \times 35$     (A1)

$= 2 \times 56 - 3 \times (315 - 5 \times 56)$

$= 17 \times 56 - 3 \times 315$     (A1)

therefore $56 \times 51 + 315 \times (- 9) = 21$     M1

$x = 51,{\text{ }}y = - 9$ is a solution     (A1)

the general solution is $x = 51 + 45N$ , $y = - 9 - 8N$ , $N \in \mathbb{Z}$     A1A1

(ii)     putting N = –2 gives y = 7 which is the required value of x     A1

[9 marks]

This question was generally well answered although some candidates were unable to proceed from a particular solution of the Diophantine equation to the general solution.

This question was generally well answered although some candidates were unable to proceed from a particular solution of the Diophantine equation to the general solution.