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