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.