Convert the decimal number 51966 to base 16.

(i)     Using the Euclidean algorithm, find the greatest common divisor, d , of 901 and 612.

(ii)     Find integers p and q such that 901p + 612q = d .

(iii)     Find the least possible positive integers s and t such that 901s − 612t = 85.

In each of the following cases find the solutions, if any, of the given linear congruence.

(i)     $9x \equiv 3(\bmod 18)$

(ii)     $9x \equiv 3(\bmod 15)$

the relevant powers of 16 are 16, 256 and 4096 

then 

$51966 = 12 \times 4096{\text{ remainder }}2814$     M1A1

$2814 = 10 \times 256{\text{ remainder }}254$

$254 = 15 \times 16{\text{ remainder }}14$     A1

the hexadecimal number is CAFE     A1

Note: CAFE is produced using a standard notation, accept explained alternative notations.

[4 marks]

(i)     using the Euclidean Algorithm     (M1)

$901 = 612 + 289$     (A1)

$612 = 2 \times 289 + 34$

$289 = 8 \times 34 + 17$

$\gcd (901,{\text{ }}612) = 17$     A1

(ii)     working backwards     (M1)

$17 = 289 - 8 \times 34$

$= 289 - 8 \times (612 - 2 \times 289)$

$= 17 \times (901 - 612) - 8 \times 612$

$= 27 \times 901 - 25 \times 612$

${\text{so }}p = 17,{\text{ }}q = - 25$     A1A1

(iii)     a particular solution is

$s = 5p = 85,{\text{ }}t = - 5q = 125$     (A1)

the general solution is

$s = 85 + 36\lambda ,{\text{ }}t = 125 + 53\lambda$     M1A1

by inspection the solution satisfying all conditions is

$(\lambda = - 2),{\text{ }}s = 13,{\text{ }}t = 19$     A1

[10 marks]

(i)     the congruence is equivalent to $9x = 3 + 18\lambda$     (A1)

this has no solutions as 9 does not divide the RHS     R1

(ii)     the congruence is equivalent to $3x = 1 + 5\lambda ,{\text{ }}\left( {3x \equiv 1(\bmod 5)} \right)$     A1

one solution is $x = 2$ , so the general solution is $x = 2 + 5n\,\,\,\,\,\left( {x \equiv 2(\bmod 5)} \right)$     M1A1

[5 marks]

Many did not seem familiar with hexadecimal notation and often left their answer as 12101514 instead of CAFE.

The Euclidean algorithm was generally found to be easy to deal with but getting a general solution in part (iii) eluded many candidates.

Rewriting the congruence in the form $9x = 3 + 18\lambda$ for example was not often seen but should have been the first thing thought of.