Use the Euclidean algorithm to show that 1463 and 389 are relatively prime.

Find positive integers \(a\) and \(b\) such that \[1463a - 389b = 1\].

\(1463 = 3 \times 389 + 296\)    M1A1

\(389 = 1 \times 296 + 93\)

\(296 = 3 \times 93 + 17\)    A1

\(93 = 5 \times 17 + 8\)

\(17 = 2 \times 8 + 1\) which shows that the gcd is 1     A1

hence 1463 and 389 are relatively prime     AG

[4 marks]

EITHER

\(1 = 17 - 2 \times 8\)    (M1)

\( = 17 - 2 \times (93 - 5 \times 17) = 11 \times 17 - 2 \times 93\)    (A1)

\( = 11 \times (296 - 3 \times 93) - 2 \times 93 = 11 \times 296 - 35 \times 93\)    (A1)

\( = 11 \times 296 - 35 \times (389 - 296) = 46 \times 296 - 35 \times 389\)

\( = 46 \times (1463 - 3 \times 389) - 35 \times 389\)    (A1)

\( = 46 \times 1463 - 173 \times 389\)    A1

\((a = 46,{\text{ }}b = 173)\)

OR

method of keeping track of the linear combinations from the beginning (could be seen alongside the working in (a))

     (M1)(A1)

     (A1)

\( - 5( - 15,{\text{ }}4)\)

\((79,{\text{ }} - 21)\)    (A1)

so \( - 173 \times 389 + 46 \times 1463 = 1\) giving \(46 \times 1463 - 173 \times 389 = 1\)     A1

\((a = 46,{\text{ }}b = 173)\)

Note:     Accept any positive answers of the form \(a = 46 + 389t,{\text{ }}b = 173 + 1463t,{\text{ }}t\) an integer.

[5 marks]

Very well answered. Some candidates lost the final mark by not saying that their working showed that the greatest common divisor (gcd) was 1.

The working backwards method was generally well known but there were arithmetic mistakes. Some candidates did not realise that their aim was to keep 1 as a combination of two remainders. The final answer could have been checked with the calculator as could intermediary steps. What was sadly less well known was the linear combinations format of laying the work out. See the OR method in the mark scheme. This makes the numerical work much less tedious and deserves to be better known.