Use the Euclidean Algorithm to show that \(275\) and \(378\) are relatively prime.

Find the general solution to the diophantine equation \(275x + 378y = 1\) .

\(378 = 1 \times 275 + 103\)     A1

\(275 = 2 \times 103 + 69\)     A1

\(103 = 1 \times 69 + 34\)     A1

\(69 = 2 \times 34 + 1\)     A1

showing that gcd \( = 1\) , i.e. relatively prime.     R1

[5 marks]

Working backwards,

\(1 = 69 - 2 \times (103 - 69)\)     (M1)

\( = 3 \times 69 - 2 \times 103\)     (A1)

\( = 3 \times (275 - 2 \times 103) - 2 \times 103\)

\( = 3 \times 275 - 8 \times 103\)     (A1)

\( = 3 \times 275 - 8 \times (378 - 275)\)

\( = 11 \times 275 - 8 \times 378\)     (A1)

A solution is \(x = 11\) , \(y = - 8\)     (A1)

The general solution is \(x = 11 + 378n\) , \(y =  - 8 - 275n\) where \(n \in \mathbb{Z}\)      M1A1     N6

[7 marks]