Use the Euclidean algorithm to find the greatest common divisor of 264 and 1365.

Hence, or otherwise, find the general solution of the Diophantine equation

$$264x - 1365y = 3.$$

Hence find the general solution of the Diophantine equation

$$264x - 1365y = 6.$$

By expressing each of 264 and 1365 as a product of its prime factors, determine the lowest common multiple of 264 and 1365.

$1365 = 5 \times 264 + 45$     M1

$264 = 5 \times 45 + 39$     A1

$45 = 1 \times 39 + 6$     A1

$39 = 6 \times 6 + 3$

$6 = 2 \times 3$     A1

so gcd is 3

[5 marks]

EITHER

$39 - 6 \times 6 = 3$     (M1)

$39 - 6 \times (45 - 39) = 3 \Rightarrow 7 \times 39 - 6 \times 45 = 3$     (A1)

$7 \times (264 - 5 \times 45) - 6 \times 45 = 3 \Rightarrow 7 \times 264 - 41 \times 45 = 3$     (A1)

$7 \times 264 - 41 \times (1365 - 5 \times 264) = 3 \Rightarrow 212 \times 264 - 41 \times 1365 = 3$     (A1)

OR

tracking the linear combinations when applying the Euclidean algorithm (could be displayed in (a))

THEN

a solution is $x = 212,y = 41$ (or equivalent eg $x = - 243,y = - 47$)     (A1)

$x = 212 + 455N,y = 41 + 88N$ (or equivalent) $(N \in \mathbb{Z})$     A1

[6 marks]

a solution is $x = 424,y = 82{\text{ }}({\text{or equivalent }}eg{\text{ }}x = - 31,{\text{ }}y = - 6)$     (A1)

$x = 424 + 455N,{\text{ }}y = 82 + 88N({\text{or equivalent}}){\text{ }}\left( {N \in \mathbb{Z}} \right)$     A1

Note:     Award A1A0 for $x = 424 + 910N,{\text{ }}y = 82 + 176N$.

[2 marks]

$264 = 2 \times 2 \times 2 \times 3 \times 11$     A1

$1365 = 3 \times 5 \times 7 \times 13$     A1

$1\,{\text{cm}} = 2 \times 2 \times 2 \times 3 \times 5 \times 7 \times 11 \times 13 = 120120$     A1

Note:     Only award marks if prime factorisation is used.

[3 marks]