Consider the integers $a = 871$ and $b= 1157$, given in base $10$.

(i)     Express $a$ and $b$ in base $13$.

(ii)     Hence show that ${\text{gcd}}(a,{\text{ }}b) = 13$.

A list $L$ contains $n+ 1$ distinct positive integers. Prove that at least two members of $L$leave the same remainder on division by $n$.

Consider the simultaneous equations

     $4x + y + 5z = a$

     $2x + z = b$

     $3x + 2y + 4z = c$

where $x,{\text{ }}y,{\text{ }}z \in \mathbb{Z}$.

(i)     Show that 7 divides $2a + b - c$.

(ii)     Given that a = 3, b = 0 and c = −1, find the solution to the system of equations modulo 2.

Consider the set $P$ of numbers of the form ${n^2} - n + 41,{\text{ }}n \in \mathbb{N}$.

(i)     Prove that all elements of P are odd.

(ii)     List the first six elements of P for n = 0, 1, 2, 3, 4, 5.

(iii)     Show that not all elements of P are prime.

(i)     METHOD 1

using a relevant list of powers of 13: (1), 13, 169, (2197)     M1

$871 = 5 \times {13^2} + 2 \times 13$     A1

$871 = {520_{13}}$     A1

$1157 = 6 \times {13^2} + 11 \times 13$     A1

$1157 = 6{\text{B}}{{\text{0}}_{13}}$     A1

METHOD 2

attempted repeated division by 13     M1

$871 \div 13 = 67;{\text{ }}67 \div 13 = 5{\text{rem}}2$     A1

$871 = {520_{13}}$     A1

$1157 \div 13 = 89;{\text{ }}89 \div 13 = 6{\text{rem11}}$     A1

$1157 = 6{\text{B}}{{\text{0}}_{13}}$     A1

Note:     Allow (11) for B only if brackets or equivalent are present.

(ii)     $871 = 13 \times 67;{\text{ }}1157 = 13 \times 89$     (M1)

67 and 89 are primes (base 10) or they are co-prime     A1

So $\gcd (871,{\text{ }}1157) = 13$     AG

Note:     Must be done by hence not Euclid’s algorithm on 871 and 1157.

[7 marks]

let K be the set of possible remainders on division by n     (M1)

then $K = \{ {\text{0, 1, 2, }} \ldots n - 1\}$ has n members     A1

because $n < n + 1{\text{ }}\left( { = n(L)} \right)$     A1

by the pigeon-hole principle (appearing anywhere and not necessarily mentioned by name as long as is explained)     R1

at least two members of L correspond to one member of K     AG

[4 marks]

(i)     form the appropriate linear combination of the equations:     (M1)

$2a + b - c = 7x + 7z$     A1

$= 7(x + z)$     R1

so 7 divides $2a + b - c$     AG

(ii)     modulo 2, the equations become     M1

$y + z = 1$

$z = 0$     A1

$x = 1$

solution: (1, 1, 0)     A1

Note:     Award full mark to use of GDC (or done manually) to solve the system giving $x =  - 1,{\text{ }}y =  - 3,{\text{ }}z = 2$ and then converting mod 2.

[6 marks]

(i)     separate consideration of even and odd n     M1

${\text{eve}}{{\text{n}}^2} - {\text{even}} + {\text{odd is odd}}$     A1

${\text{od}}{{\text{d}}^2} - {\text{odd}} + {\text{odd is odd}}$     A1

all elements of P are odd     AG

Note:     Allow other methods eg, ${n^2} - n = n(n - 1)$ which must be even.

(ii)     the list is [41, 41, 43, 47, 53, 61]     A1

(iii)     ${41^2} - 41 + 41 = {41^2}$ divisible by 41     A1

but is not a prime     R1

the statement is disproved (by counterexample)  AG

[6 marks]