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]