(a)     Use the Euclidean algorithm to find the gcd of 324 and 129.

(b)     Hence show that $324x + 129y = 12$ has a solution and find both a particular solution and the general solution.

(c)     Show that there are no integers x and y such that $82x + 140y = 3$ .

(a)     $324 = 2 \times 129 + 66$     M1

$129 = 1 \times 66 + 63$

$66 = 1 \times 63 + 3$     A1

hence gcd (324, 129) = 3     A1

[3 marks]

(b)     METHOD 1

Since $\left. 3 \right|12$ the equation has a solution     M1

$3 = 1 \times 66 - 1 \times 63$     M1

$3 = - 1 \times 129 + 2 \times 66$

$3 = 2 \times (324 - 2 \times 129) - 129$

$3 = 2 \times 324 - 5 \times 129$     A1

$12 = 8 \times 324 - 20 \times 129$     A1

$(x,\,y) = (8,\, - 20)$ is a particular solution     A1

Note: A calculator solution may gain M1M1A0A0A1.

A general solution is $x = 8 + \frac{{129}}{3}t = 8 + 43t,{\text{ }}y = - 20 - 108t,{\text{ }}t \in \mathbb{Z}$     A1

METHOD 2

$324x + 129y = 12$

$108x + 43y = 4$     A1

$108x \equiv 4(\bmod 43) \Rightarrow 27x \equiv 1(\bmod 43)$     A1

$x = 8 + 43t$     A1

$108(8 + 43t) + 43y = 4$     M1

$864 + 4644t + 43y = 4$

$43y = - 860 - 4644t$

$y = - 20 - 108t$     A1

a particular solution (for example $t = 0$) is $(x,\,y) = (8,\, - 20)$     A1

[6 marks]

(c)     EITHER

The left side is even and the right side is odd so there are no solutions     M1R1AG

[2 marks]

OR

$\gcd (82,\,140) = 2$     A1

2 does not divide 3 therefore no solutions     R1AG

[2 marks]

Total [11 marks]

This problem was not difficult but presenting a clear solution and doing part (b) alongside part (a) in two columns was. The simple answer to part (c) was often overlooked.