## Question

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.

**Answer/Explanation**

## Markscheme

(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]*

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

## Question

Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices and in which every vertex is connected to at least one other vertex, there must be at least two vertices with the same degree.

Seventeen people attend a meeting.

Each person shakes hands with at least one other person and no-one shakes hands with

the same person more than once. Use the result from part (a) to show that there must be at least two people who shake hands with the same number of people.

Explain why each person cannot have shaken hands with exactly nine other people.

**Answer/Explanation**

## Markscheme

let there be *\(v\) *vertices in the graph; because the graph is simple the degree of each vertex is \( \le v – 1\) *A1*

the degree of each vertex is \( \ge 1\) *A1*

there are therefore \(v – 1\) possible values for the degree of each vertex *A1*

given there are *\(v\) *vertices by the pigeon-hole principle there must be at least two with the same degree *R1*

*[4 marks]*

consider a graph in which the people at the meeting are represented by the vertices and two vertices are connected if the two people shake hands *M1*

the graph is simple as no-one shakes hands with the same person more than once (nor can someone shake hands with themselves) *A1*

every vertex is connected to at least one other vertex as everyone shakes at least one hand *A1*

the degree of each vertex is the number of handshakes so by the proof above there must be at least two who shake the same number of hands *R1*

**Note: **Accept answers starting afresh rather than quoting part (a).

**[4 marks]**

(the handshaking lemma tells us that) the sum of the degrees of the vertices must be an even number *A1*

the degree of each vertex would be *\(9\)* and \(9 \times 17\) is an odd number (giving a contradiction) *A1*

*[2 marks]*

*Total [10 marks]*

## Examiners report

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Misconceptions were: thinking that a few examples constituted a proof, thinking that the graph had to be connected, taking the edges as the pigeons not the degrees. The pigeon-hole principle was known but not always applied well.

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Similar problems as in (a).

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Many spurious reasons were given but good candidates went straight to the hand-shaking lemma.

## Question

The Fibonacci sequence can be described by the recurrence relation \({f_{n + 2}} = {f_{n + 1}} + {f_n}\) where \({f_0} = 0,\,{f_1} = 1\).

Write down the auxiliary equation and use it to find an expression for \({f_n}\) in terms of \(n\).

It is known that \({\alpha ^2} = \alpha + 1\) where \(\alpha = \frac{{1 + \sqrt 5 }}{2}\).

For integers \(n\) ≥ 3, use strong induction on the recurrence relation \({f_{n + 2}} = {f_{n + 1}} + {f_n}\) to prove that \({f_n} > {\alpha ^{n – 2}}\).

**Answer/Explanation**

## Markscheme

attempt to find the auxiliary equation (\({\lambda ^2} – \lambda – 1 = 0\)) **M1**

\(\lambda = \frac{{1 \pm \sqrt 5 }}{2}\) ** (A1)**

the general solution is \({f_n} = A{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} + B{\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n}\) ** (M1)**

imposing initial conditions (substituting \(n\) = 0,1) **M1**

*A* + *B* = 0 and \(A\left( {\frac{{1 + \sqrt 5 }}{2}} \right) + B\left( {\frac{{1 – \sqrt 5 }}{2}} \right) = 1\) **A1**

\(A = \frac{1}{{\sqrt 5 }},\,\,B = – \frac{1}{{\sqrt 5 }}\) **A1**

\({f_n} = \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} – \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n}\) **A1**

**Note:** Condone use of decimal numbers rather than exact answers.

**[7 marks]**

let P(\(n\)) be \({f_n} > {\alpha ^{n – 2}}\) for integers \(n\) ≥ 3

consideration of two consecutive values of \(f\) **R1**

\({f_3} = 2\) and \({\alpha ^{3 – 2}} = \frac{{1 + \sqrt 5 }}{2}\left( {1.618 \ldots } \right) \Rightarrow {\text{P}}\left( 3 \right)\) is true **A1**

\({f_4} = 3\) and \({\alpha ^{4 – 2}} = \frac{{3 + \sqrt 5 }}{2}\left( {2.618 \ldots } \right) \Rightarrow {\text{P}}\left( 4 \right)\) is true **A1**

**Note:** Do not award * A* marks for values of \(n\) other than \(n\) = 3 and \(n\) = 4.

(for \(k\) ≥ 4), assume that P(\(k\)) and P(\(k\) − 1) are true **M1**

required to prove that P(\(k\) + 1) is true

**Note:** Accept equivalent notation. Needs to start with 2 general consecutive integers and then prove for the next integer. This will affect the powers of the alphas.

\({f_{k + 1}} = {f_k} + {f_{k – 1}}\) (and \({f_k} > {\alpha ^{k – 2}},\,{f_{k – 1}} > {\alpha ^{k – 3}}\)) **M1**

\({f_{k + 1}} > {\alpha ^{k – 2}} + {\alpha ^{k – 3}} = {\alpha ^{k – 3}}\left( {\alpha + 1} \right)\) **A1**

\( = {\alpha ^{k – 3}}{\alpha ^2} = {\alpha ^{k – 1}} = {\alpha ^{\left( {k + 1} \right) – 2}}\) **A1**

as P(3) and P(4) are true, and P(\(k\)) , P(\(k\) − 1) true ⇒ P(\(k\) + 1) true then P(\(k\)) is true for \(k\) ≥ 3 by strong induction **R1**

**Note:** To obtain the final * R1*, at least five of the previous marks must have been awarded.

**[8 marks]**

## Examiners report

[N/A]

[N/A]