## Question

(i) Given that \(a \equiv d(\bmod n)\) and \(b \equiv c(\bmod n)\) prove that

\[(a + b) \equiv (c + d)(\bmod n){\text{ .}}\]

(ii) Hence solve the system

\[\left\{ {\begin{array}{*{20}{r}}

{2x + 5y \equiv 1(\bmod 6)} \\

{x + y \equiv 5(\bmod 6)}

\end{array}} \right.\]

Show that \({x^{97}} – x + 1 \equiv 0(\bmod 97)\) has no solution.

**Answer/Explanation**

## Markscheme

(i) \(a \equiv d(\bmod n){\text{ and }}b \equiv c(\bmod n)\)

so \(a – d = pn{\text{ and }}b – c = qn\) , *M1A1*

\(a – d + b – c = pn + qn\)

\((a + b) – (c + d) = n(p + q)\) *A1*

\((a + b) \equiv (c + d)(\bmod n)\) *AG*

(ii) \(\left\{ {\begin{array}{*{20}{r}}

{2x + 5y \equiv 1(\bmod 6)} \\

{x + y \equiv 5(\bmod 6)}

\end{array}} \right.\)

adding \(3x + 6y \equiv 0(\bmod 6)\) *M1*

\(6y \equiv 0(\bmod 6){\text{ so }}3x \equiv 0(\bmod 6)\) *R1*

\(x \equiv 0{\text{ or }}x \equiv 2{\text{ or }}x \equiv 4(\bmod 6)\) *A1A1A1*

for \(x \equiv 0,{\text{ }}0 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 5(\bmod 6)\) *A1*

for \(x \equiv 2,{\text{ }}2 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 3(\bmod 6)\) *A1*

If \(x \equiv 4(\bmod 6),{\text{ }}4 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 1(\bmod 6)\) *A1*

*[11 marks]*

Suppose *x *is a solution

97 is prime so \({x^{97}} \equiv x(\bmod 97)\) *M1*

\({x^{97}} – x \equiv 0(\bmod 97)\) *A1*

\({x^{97}} – x + 1 \equiv 1 \ne 0(\bmod 97)\)

Hence there are no solutions *R1*

*[3 marks]*

## Examiners report

Part (a) (i) was not found difficult but using it in part (a)(ii) resulted in two or three correct lines and then abandonment of the problem.

Part (a) (i) was not found difficult but using it in part (a)(ii) resulted in two or three correct lines and then abandonment of the problem.

## Question

Write 57128 as a product of primes.

Prove that \(\left. {22} \right|{5^{11}} + {17^{11}}\).

**Answer/Explanation**

## Markscheme

\(457\,128 = 2 \times 228\,564\)

\(228\,564 = 2 \times 114\,282\)

\(114\,282 = 2 \times 57\,141\)

\(57\,141 = 3 \times 19\,047\)

\(19\,047 = 3 \times 6349\)

\(6349 = 7 \times 907\) *M1A1*

trial division by 11, 13, 17, 19, 23 and 29 shows that 907 is prime *R1*

therefore \(457\,128 = {2^3} \times {3^2} \times 7 \times 907\) *A1*

*[4 marks]*

by a corollary to Fermat’s Last Theorem

\({5^{11}} \equiv 5(\bmod 11){\text{ and }}{17^{11}} \equiv 17(\bmod 11)\) *M1A1*

\({5^{11}} + {17^{11}} \equiv 5 + 17 \equiv 0(\bmod 11)\) *A1*

this combined with the evenness of LHS implies \(\left. {25} \right|{5^{11}} + {17^{11}}\) *R1AG*

*[4 marks]*

## Examiners report

Some candidates were obviously not sure what was meant by ‘product of primes’ which surprised the examiner.

There were some reasonable attempts at part (c) using powers rather than Fermat’s little theorem.

## Question

(a) Using Fermat’s little theorem, show that, in base 10, the last digit of *n* is always equal to the last digit of \({n^5}\) .

(b) Show that this result is also true in base 30.

**Answer/Explanation**

## Markscheme

(a) using Fermat’s little theorem \({n^5} \equiv n(\bmod 5)\) *(M1)*

\({n^5} – n \equiv 0(\bmod 5)\) *A1*

now \({n^5} – n = n({n^4} – 1)\) *(M1)*

\( = n({n^2} – 1)({n^2} + 1)\)

\( = n(n – 1)(n + 1)({n^2} + 1)\) *A1*

hence one of the first two factors must be even *R1*

*i.e.* \({n^5} – n \equiv 0(\bmod 2)\)

thus \({n^5} – n\) is divisible by 5 and 2

hence it is divisible by 10 *R1*

in base 10, since \({n^5} – n\) is divisible by 10, then \({n^5} – n\) must end in zero and hence \({n^5}\) and *n* must end with the same digit *R1*

*[7 marks]*

* *

(b) consider \({n^5} – n = n(n – 1)(n + 1)({n^2} + 1)\)

this is divisible by 3 since the first three factors are consecutive integers *R1*

hence \({n^5} – n\) is divisible by 3, 5 and 2 and therefore divisible by 30

in base 30, since \({n^5} – n\) is divisible by 30, then \({n^5} – n\) must end in zero and hence \({n^5}\) and *n* must end with the same digit *R1*

*[2 marks]*

*Total [9 marks]*

## Examiners report

There were very few fully correct answers. If Fermat‟s little theorem was known, it was not well applied.

## Question

Show that a positive integer, written in base 10, is divisible by 9 if the sum of its digits is divisible by 9.

The representation of the positive integer *N* in base *p* is denoted by \({(N)_p}\) .

If \({({5^{{{(126)}_7}}})_7} = {({a_n}{a_{n – 1}} \ldots {a_1}{a_0})_7}\) , find \({a_0}\) .

**Answer/Explanation**

## Markscheme

consider the decimal number \(A = {a_n}{a_{n – 1}} \ldots {a_0}\) *M1*

\(A = {A_n} \times {10^n} + {a_{n – 1}} \times {10^{n – 1}} + \ldots + {a_1} \times 10 + {a_0}\) *M1*

\( = {a_n} \times ({10^n} – 1) + {a_{n – 1}} \times ({10^{n – 1}} – 1) + \ldots + {a_1} \times (10 – 1) + {a_n} + {a_{n – 1}} + \ldots + {a_0}\) *M1A1*

\( = {a_n} \times 99 \ldots 9(n{\text{ digits}}) + {a_{n – 1}} \times 99 \ldots 9(n – 1{\text{ digits}}) + \ldots + 9{a_1} + {a_n} + {a_{n – 1}} + \ldots + {a_0}\) *A1*

all the numbers of the form 99…9 are divisible by 9 (to give 11…1), *R1*

hence *A* is divisible by 9 if \(\sum\limits_{i = 0}^n {{a_i}} \) is divisible by 9 *R1*

**Note:** A method that uses the fact that \({10^t} \equiv 1(\bmod 9)\) is equally valid.

*[7 marks]*

by Fermat’s Little Theorem \({5^6} \equiv 1(\bmod 7)\) *M1A1*

\({(126)_7} = {(49 + 14 + 6)_{10}} = {(69)_{10}}\) *M1A1*

\({5^{{{(126)}_7}}} \equiv {5^{{{(11 \times 6 + 3)}_{10}}}} \equiv {5^{{{(3)}_{10}}}}(\bmod 7)\) *M1A1*

\({5^{{{(3)}_{10}}}} = {(125)_{10}} = {(17 \times 7 + 6)_{10}} \equiv 6(\bmod 7)\) *M1A1*

hence \({a_0} = 6\) *A1*

*[9 marks]*

## Examiners report

Questions similar to (a) have been asked in the past so it was surprising to see that solutions this time were generally disappointing.

In (b), most candidates changed the base 7 number 126 to the base 10 number 69. After that the expectation was that Fermat’s little theorem would be used to complete the solution but few candidates actually did that. Many were unable to proceed any further and others used a variety of methods, for example working modulo 7,

\({5^{69}} = {({5^2})^{34}}.5 = {4^{34}}.5 = {({4^2})^{17}}.5 = {2^{17}}.5\) etc

This is of course a valid method, but somewhat laborious.

## Question

(i) One version of Fermat’s little theorem states that, under certain conditions,

\[{a^{p – 1}} \equiv 1(\bmod p).\]

Show that this result is not valid when *a* = 4, *p* = 9 and state which

condition is not satisfied.

(ii) Given that \({5^{64}} \equiv n(\bmod 7)\), where \(0 \leqslant n \leqslant 6\), find the value of *n*.

Find the general solution to the simultaneous congruences

\[x \equiv 3(\bmod 4)\]

\[3x \equiv 2(\bmod 5).\]

**Answer/Explanation**

## Markscheme

(i) \({4^8} = 65536 \equiv 7(\bmod 9)\) *A1*

not valid because 9 is not a prime number *R1*

**Note:** The ** R1** is independent of the

**.**

*A1*

(ii) using Fermat’s little theorem *M1*

\({5^6} \equiv 1(\bmod 7)\) *A1*

therefore

\({({5^6})^{10}} = {5^{60}} \equiv 1(\bmod 7)\) *A1*

also, \({5^4} = 625\) *M1*

\( \equiv 2(\bmod 7)\) *A1*

therefore

\({5^{64}} \equiv 1 \times 2 \equiv 2(\bmod 7)\,\,\,\,\,{\text{(so }}n = 2)\) *A1*

**Note:** Accept alternative solutions not using Fermat.

*[8 marks]*

**EITHER**

solutions to \(x \equiv 3(\bmod 4)\) are

3, 7, 11, 15, 19, 23, 27, … *A1*

solutions to \(3x \equiv 2(\bmod 5).\) are

4, 9, 14, 19 … *(M1)A1*

so a solution is *x* =19 *A1*

using the Chinese remainder theorem (or otherwise) *(M1)*

the general solution is \(x = 19 + 20n{\text{ }}(n \in \mathbb{Z})\) *A1*

\(\left( {{\text{accept }}19(\bmod 20)} \right)\)

**OR**

\(x = 3 + 4t \Rightarrow 9 + 12t \equiv 2(\bmod 5)\) *M1A1*

\( \Rightarrow 2t \equiv 3(\bmod 5)\) *A1*

\( \Rightarrow 6t \equiv 9(\bmod 5)\)

\( \Rightarrow t \equiv 4(\bmod 5)\) *A1*

so \(t = 4 + 5n{\text{ and }}x = 19 + 20n{\text{ }}(n \in \mathbb{Z})\) *M1A1*

\(\left( {{\text{accept }}19(\bmod 20)} \right)\)

**Note:** Also accept solutions done by formula.

*[6 marks]*

## Examiners report

Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg \({5^4} \equiv 2,{\text{ }}{5^8} \equiv 4\) and \({5^3}\equiv- 1(\bmod 7)\) were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to \(3(\bmod 4)\)and \(4(\bmod 5)\) and the use of an appropriate formula.

Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg \({5^4} \equiv 2,{\text{ }}{5^8} \equiv 4\) and \({5^3}\equiv – 1(\bmod 7)\) were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to \(3(\bmod 4)\)and \(4(\bmod 5)\) and the use of an appropriate formula.

## Question

(a) Write down Fermat’s little theorem.

(b) In base 5 the representation of a natural number *X* is \({\left( {k00013(5 – k)} \right)_5}\).

This means that \(X = k \times {5^6} + 1 \times {5^2} + 3 \times 5 + (5 – k)\).

In base 7 the representation of *X* is \({({a_n}{a_{n – 1}} \ldots {a_2}{a_1}{a_0})_7}\).

Find \({a_0}\).

(c) Given that *k* = 2, find *X* in base 7.

**Answer/Explanation**

## Markscheme

(a) **EITHER**

if *p* is a prime \({a^p} \equiv a(\bmod p)\) *A1A1*

**OR**

if *p* is a prime and \(a\) \(0(\bmod p)\) then \({a^{p – 1}} \equiv 1(\bmod p)\) *A1A1*

**Note:** Award ** A1** for

*p*being prime and

**for the congruence.**

*A1**[2 marks]*

(b) \({a_0} \equiv X(\bmod 7)\) *M1*

\(X = k \times {5^6} + 25 + 15 + 5 – k\)

by Fermat \({5^6} \equiv 1(\bmod 7)\) *R1*

\(X = k + 45 – k(\bmod 7)\) *(M1)*

\(X = 3(\bmod 7)\) *A1*

\({a_0} = 3\) *A1*

*[5 marks]*

(c) \(X = 2 \times {5^6} + 25 + 15 + 3 = 31\,293\) *A1*

**EITHER**

\(X – {7^5} = 14\,486\) *(M1)*

\(X – {7^5} – 6 \times {7^4} = 80\)

\(X – {7^5} – 6 \times {7^4} – {7^2} = 31\)

\(X – {7^5} – 6 \times {7^4} – {7^2} – 4 \times 7 = 3\)

\(X = {7^5} + 6 \times {7^4} + {7^2} + 4 \times 7 + 3\) *(A1)*

\(X = {(160\,143)_7}\) *A1*

**OR**

\(31\,293 = 7 \times 4470 + 3\) *(M1)*

\(4470 = 7 \times 638 + 4\)

\(638 = 7 \times 91 + 1\)

\(91 = 7 \times 13 + 0\)

\(13 = 7 \times 1 + 6\) *(A1)*

\(X = {(160\,143)_7}\) *A1*

*[4 marks]*

*Total [11 marks]*

## Examiners report

Fermat’s little theorem was reasonably well known. Not all candidates took the hint to use this in the next part and this part was not done well. Part (c) could and was done even if part (b) was not.

## Question

A version of Fermat’s little theorem states that when *p* is prime, *a* is a positive integer and *a* and *p* are relatively prime, then \({a^{p – 1}} \equiv 1(\bmod p)\).

Use the above result to show that if *p* is prime then \({a^p} \equiv a(\bmod p)\) where *a* is any positive integer.

Show that \({2^{341}} \equiv 2(\bmod 341)\).

(i) State the converse of the result in part (a).

(ii) Show that this converse is not true.

**Answer/Explanation**

## Markscheme

consider two cases *M1*

let *a* and *p* be coprime

\({a^{p – 1}} \equiv 1(\bmod p)\) *R1*

\( \Rightarrow {a^p} \equiv a(\bmod p)\)

let *a* and *p* not be coprime

\(a \equiv 0(\bmod p)\) *M1*

\({a^p} = 0(\bmod p)\) *R1*

\( \Rightarrow {a^p} = a(\bmod p)\)

so \({a^p} = a(\bmod p)\) in both cases *AG*

*[4 marks]*

\(341 = 11 \times 31\) *(M1)*

we know by Fermat’s little theorem

\({2^{10}} \equiv 1(\bmod 11)\) *M1*

\( \Rightarrow {2^{341}} \equiv {({2^{10}})^{34}} \times 2 \equiv {1^{34}} \times 2 \equiv 2(\bmod 11)\) *A1*

also \({2^{30}} \equiv 1(\bmod 31)\) *M1*

\( \Rightarrow {2^{341}} \equiv {({2^{30}})^{11}} \times {2^{11}}\) *A1*

\( \equiv {1^{11}} \times 2048 \equiv 2(\bmod 31)\) *A1*

since 31 and 11 are coprime *R1*

\({2^{341}} \equiv 2(\bmod 341)\) *AG*

*[7 marks]*

(i) converse: if \({a^p} = a(\bmod p)\) then *p* is a prime *A1*

* *

(ii) from part (b) we know \({2^{341}} \equiv 2(\bmod 341)\)

however, 341 is composite

hence 341 is a counter-example and the converse is not true *R1*

*[2 marks]*

## Examiners report

There were very few fully correct answers. In (b) the majority of candidates assumed that 341 is a prime number and in (c) only a handful of candidates were able to state the converse.

There were very few fully correct answers. In (b) the majority of candidates assumed that 341 is a prime number and in (c) only a handful of candidates were able to state the converse.

There were very few fully correct answers. In (b) the majority of candidates assumed that 341 is a prime number and in (c) only a handful of candidates were able to state the converse.

## Question

Use the result \(2003 = 6 \times 333 + 5\) and Fermat’s little theorem to show that \({2^{2003}} \equiv 4(\bmod 7)\) .

Find \({2^{2003}}(\bmod 11)\) and \({2^{2003}}(\bmod 13)\).

Use the Chinese remainder theorem, or otherwise, to evaluate \({2^{2003}}(\bmod 1001)\), noting that \(1001 = 7 \times 11 \times 13\).

**Answer/Explanation**

## Markscheme

\({2^{2003}} = {2^5} \times {({2^6})^{333}}\) ** M1A1**

\( \equiv 32 \times 1(\bmod 7)\) by Fermat’s little theorem *A1*

\( \equiv 4(\bmod 7)\) ** AG**

*[3 marks]*

\(2003 = 3 + 10 \times 200\) ** (M1)**

\({2^{2003}} = {2^3} \times {({2^{10}})^{200}}\left( { \equiv 8 \times 1(\bmod 11)} \right) \equiv 8(\bmod 11)\) ** A1**

\({2^{2003}} = {2^{11}} \times {({2^{12}})^{166}} \equiv 7(\bmod 13)\) ** A1**

*[3 marks]*

form \({M_1} = \frac{{1001}}{7} = 143;{\text{ }}{M_2} = \frac{{1001}}{{11}} = 91;{\text{ }}{M_3} = \frac{{1001}}{{13}} = 77\) *M1*

solve \(143{x_1} \equiv 1(\bmod 7) \Rightarrow {x_1} = 5\) *M1A1*

\({x_2} = 4;{\text{ }}{x_3} = 12\) ** A1A1**

\(x = 4 \times 143 \times 5 + 8 \times 91 \times 4 + 7 \times 77 \times 12 = 12240 \equiv 228(\bmod 1001)\) ** M1A1**

*[7 marks]*

## Examiners report

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

## Question

State Fermat’s little theorem.

**Answer/Explanation**

## Markscheme

if *p *is a prime (and \(a \equiv 0(\bmod p)\) with \(a \in \mathbb{Z}\)) then *A1*

\({a^{p – 1}} \equiv 1(\bmod p)\) *A1*

*[2 marks]*** **

**Note**: Accept \({a^p} \equiv a(\bmod p)\) .

## Examiners report

Fermat’s little theorem was reasonably well known. Some candidates forgot to mention that *p *was a prime. Not all candidates took the hint to use this in the next part.

## Question

The positive integer *p* is an odd prime number.

Show that \(\sum\limits_{k = 1}^p {{k^p} \equiv 0(\bmod p)} \).

Given that \(\sum\limits_{k = 1}^p {{k^{p – 1}} \equiv n(\bmod p)} \) where \(0 \leqslant n \leqslant p – 1\), find the value of *n*.

**Answer/Explanation**

## Markscheme

using Fermat’s little theorem,

\({k^p} \equiv k(\bmod p)\) *(M1)*

therefore,

\(\sum\limits_{k = 1}^p {{k^p} \equiv } \sum\limits_{k = 1}^p {k(\bmod p)} \) *M1*

\( \equiv \frac{{p(p + 1)}}{2}(\bmod p)\) *A1*

\( \equiv 0(\bmod p)\) *AG*

since \(\frac{{(p + 1)}}{2}\) is an integer (so that the right-hand side is a multiple of *p*) *R1*

*[4 marks]*

using the alternative form of Fermat’s little theorem,

\({k^{p – 1}} \equiv 1(\bmod p),{\text{ }}1 \leqslant k \leqslant p – 1\) *A1*

\({k^{p – 1}} \equiv 0(\bmod p),{\text{ }}k = p\) *A1*

therefore,

\(\sum\limits_{k = 1}^p {{k^{p – 1}} \equiv } \sum\limits_{k = 1}^{p – 1} {1{\text{ }}( + 0)(\bmod p)} \) *M1*

\( \equiv p – 1(\bmod p)\) *A1*

(so *n* = *p* − 1)

**Note:** Allow first ** A1** even if qualification on

*k*is not given.

* *

*[4 marks]*

## Examiners report

Only the top candidates were able to produce logically, well thought-out proofs. Too many candidates struggled with the summation notation and were not able to apply Fermat’s little theorem. There was poor logic i.e. looking at a particular example and poor algebra.

Only the top candidates were able to produce logically, well thought-out proofs. Too many candidates struggled with the summation notation and were not able to apply Fermat’s little theorem. There was poor logic i.e. looking at a particular example and poor algebra.

## Question

Let \(f(n) = {n^5} – n,{\text{ }}n \in {\mathbb{Z}^ + }\).

Find the values of \(f(3)\), \(f(4)\) and \(f(5)\).

Use the Euclidean algorithm to find

(i) \(\gcd \left( {f(3),{\text{ }}f(4)} \right)\);

(ii) \(\gcd \left( {f(4),{\text{ }}f(5)} \right)\).

Explain why \(f(n)\) is always exactly divisible by \(5\).

By factorizing \(f(n)\) explain why it is always exactly divisible by \(6\).

Determine the values of *\(n\) *for which \(f(n)\) is exactly divisible by \(60\).

**Answer/Explanation**

## Markscheme

\(240,{\rm{ }}1020,{\rm{ }}3120\) *A2*

**Note: **Award ** A2 **for three correct answers,

**for two correct answers.**

*A1***[2 marks]**

(i) \(1020 = 240 \times 4 + 60\) *(M1)*

\(240 = 60 \times 4\)

\(\gcd (1020,{\text{ }}240) = 60\) *A1*

(ii) \(3120 = 1020 \times 3 + 60\) *(M1)*

\(1020 = 60 \times 17\)

\(\gcd (1020,{\text{ }}3120) = 60\) *A1*

**Note: **Must be done by Euclid’s algorithm.

**[4 marks]**

by Fermat’s little theorem with \(p = 5\) *R1*

\({n^5} \equiv n(\bmod 5)\)

so 5 divides \(f(n)\)

**[1 mark]**

\(f(n) = n({n^2} – 1)({n^2} + 1) = n(n – 1)(n + 1)({n^2} + 1)\) *(A1)A1*

\(n – 1,{\text{ }}n,{\text{ }}n + 1\) are consecutive integers and so contain a multiple of \(2\) and \(3\) *R1R1*

**Note: **Award ** R1 **for justification of \(2\) and

**for justification of \(3\).**

*R1*And therefore \(f(n)\) is a multiple of \(6\). *AG*

*[4 marks]*

from (c) and (d) \(f(n)\) is always divisible by \(30\) *R1*

considering the factorization, it is divisible by \(60\) when *\(n\) *is an odd number *A1*

or when *\(n\) *is a multiple of \(4\) *A1*

**Note: **Accept answers such as when *\(n\) *is not congruent to \(2(\bmod 4)\).

**[3 marks]**

**Total [14 marks]**

## Examiners report

Well answered.

Also well answered. A few candidates did not use the Euclidean algorithm to find the gcd as instructed.

Many candidates essential said it was true because it was! There is only one mark which means one minute, so it must be a short answer which it is by using Fermat’s Little Theorem.

Some good answers but too many did not factorize as instructed, so that they could then spot the consecutive numbers.

Only the better candidates realised that they had to find another factor of \(2\).

## Question

Solve, by any method, the following system of linear congruences

\(x \equiv 9(\bmod 11)\)

\(x \equiv 1(\bmod 5)\)

Find the remainder when \({41^{82}}\) is divided by 11.

Using your answers to parts (a) and (b) find the remainder when \({41^{82}}\) is divided by \(55\).

**Answer/Explanation**

## Markscheme

**METHOD 1**

listing \(9,{\rm{ }}20,{\rm{ }}31\), \( \ldots \) and \(1,{\rm{ }}6,11,16,{\rm{ }}21,{\rm{ }}26,{\rm{ }}31\), \( \ldots \) *M1*

one solution is \(31\) *(A1)*

by the Chinese remainder theorem the full solution is

\(x \equiv 31(\bmod 55)\) *A1 N2*

**METHOD 2**

\(x \equiv 9(\bmod 11) \Rightarrow x = 9 + 11t\) *M1*

\( \Rightarrow 9 + 11t \equiv 1(\bmod 5)\)

\( \Rightarrow t \equiv 2(\bmod 5)\) *A1*

\( \Rightarrow t = 2 + 5s\)

\( \Rightarrow x = 9 + 11(2 + 5s)\)

\( \Rightarrow x = 31 + 55s{\text{ }}\left( { \Rightarrow x \equiv 31(\bmod 55)} \right)\) *A1*

**Note: **Accept other methods *eg *formula, Diophantine equation.

**Note: **Accept other equivalent answers e.g. \( – 79(\bmod 55)\).

**[3 marks]**

\({41^{82}} \equiv {8^{82}}(\bmod 11)\)

by Fermat’s little theorem \({8^{10}} \equiv 1(\bmod 11)\;\;\;\left( {{\text{or }}{{41}^{10}} \equiv 1(\bmod 11)} \right)\) *M1*

\({8^{82}} \equiv {8^2}(\bmod 11)\) *M1*

\( \equiv 9(\bmod 11)\) *(A1)*

remainder is \(9\) *A1*

**Note: **Accept simplifications done without Fermat.

**[4 marks]**

\({41^{82}} \equiv {1^{82}} \equiv 1(\bmod 5)\) *A1*

so \({41^{82}}\) has a remainder \(1\) when divided by \(5\) and a remainder \(9\) when divided by \(11\) *R1*

hence by part (a) the remainder is \(31\) *A1*

*[3 marks]*

*Total [10 marks]*

## Examiners report

A variety of methods were used here. The Chinese Remainder Theorem method (Method 2 on the mark-scheme) is probably the most instructive. Candidates who tried to do it by formula often (as usual) made mistakes and got it wrong. Marks were lost by just saying 31 and not giving mod (55).

Time was lost here by not using Fermat’s Little Theorem as a starting point, although the ad hoc methods will work.

Although it said use parts (a) and (b) not enough candidates saw the connection.

## Question

Show that there are exactly two solutions to the equation \(1982 = 36a + 74b\), with \(a,{\text{ }}b \in \mathbb{N}\).

Hence, or otherwise, find the remainder when \({1982^{1982}}\) is divided by \(37\).

**Answer/Explanation**

## Markscheme

\(74 = 2 \times 36 + 2\) **OR **\(\gcd (36,{\text{ }}74) = 2\) *(A1)*

\(2 = ( – 2)(36) + (1)(74)\) *M1*

\(1982 = ( – 1982)(36) + (991)(74)\) *A1*

so solutions are \(a = – 1982 + 37t\) and \(b = 991 – 18t\) *M1A1*

\(a,{\text{ }}b \in \mathbb{N}{\text{ so }}\frac{{1982}}{{37}} \le t \le \frac{{991}}{{18}}\;\;\;{\text{(}}15.56 \ldots \le t \le 55.055 \ldots )\) *(M1)(A1)*

\(t\) can take values \(54\) or \(55\) only *A1AG*

(Or the solutions are \((16,{\text{ }}19)\) or \((53,{\text{ }}1)\))

**Note: **Accept arguments from one solution of increasing/decreasing \(a\) by \(37\) and increasing/decreasing \(b\) by \(18\) to give the only possible positive solutions.

**[8 marks]**

\(1982 = 53 \times 36 + 74\)

\(1982 = 55 \times 36 + 2\) *(M1)*

\({1982^{36}} \equiv 1(\bmod 37){\text{ }}({\text{by FLT}})\) *(M1)*

\({1982^{1982}} = {1982^{36 \times 55 + 2}} \equiv {1982^2}(\bmod 37)\) *(A1)*

\( \equiv 34(\bmod 37)\) *A1*

so the remainder is \(34\) *A1*

**Note: **\(1982\) in the base can be replaced by \(21\).

**Note: **Award the first ** (M1) **if the \(1982\) in the experiment is correctly broken down to a smaller number.

**[5 marks]**

**Total [13 marks]**

## Examiners report

[N/A]

[N/A]

## Question

Consider the recurrence relation

\({u_n} = 5{u_{n – 1}} – 6{u_{n – 2}},{\text{ }}{u_0} = 0\) and \({u_1} = 1\).

Find an expression for \({u_n}\) in terms of \(n\).

For every prime number \(p > 3\), show that \(p|{u_{p – 1}}\).

**Answer/Explanation**

## Markscheme

the auxiliary equation is \({\lambda ^2} – 5\lambda + 6 = 0\) *M1*

\( \Rightarrow \lambda = 2,{\text{ }}3\) *(A1)*

the general solution is \({u_n} = A \times {2^n} + B \times {3^n}\) *A1*

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

\(A + B = 0\) and \(2A + 3B = 1\) *A1*

the solution is \(A = – 1,{\text{ }}B = 1\)

so that \({u_n} = {3^n} – {2^n}\) *A1*

*[6 marks]*

\({u_{p – 1}} = {3^{p – 1}} – {2^{p – 1}}\)

\(p > 3\), therefore 3 or 2 are not divisible by \(p\) *R1*

hence by FLT, \({3^{p – 1}} \equiv 1 \equiv {2^{p – 1}}(\bmod p)\) for \(p > 3\) *M1A1*

\({u_{p – 1}} \equiv 0(\bmod p)\) *A1*

\(p|{u_{p – 1}}\) for every prime number \(p > 3\) *AG*

*[4 marks]*

## Examiners report

[N/A]

[N/A]

## Question

Consider the linear congruence \(ax \equiv b\left( {{\text{mod}}\,p} \right)\) where \(a,\,b,\,p,\,x \in {\mathbb{Z}^ + }\), \(p\) is prime and \(a\) is not a multiple of \(p\).

State Fermat’s little theorem.

Use Fermat’s little theorem to show that \(x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)\).

Hence solve the linear congruence \(5x \equiv 7\left( {{\text{mod}}\,13} \right)\).

**Answer/Explanation**

## Markscheme

**EITHER**

if \(p\) is prime (and \(a\) is any integer) then \({a^p} \equiv a\left( {{\text{mod}}\,p} \right)\) **A1****A1**

**Note:** Award * A1 *for \(p\) prime and

*for the congruence or for stating that \(p\left| {{a^p} – a} \right.\).*

**A1****OR**

**A1****A1**

**Note:** Award * A1 *for \(p\) prime and

*for the congruence or for stating that \(p\left| {{a^{p – 1}} – 1} \right.\).*

**A1****Note:** Condone use of equals sign provided \(\left( {{\text{mod}}\,p} \right)\) is seen.

**[2 marks]**

multiplying both sides of the linear congruence by \({a^{p – 2}}\) **(M1)**

\({a^{p – 1}}x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)\) **A1**

as \({a^{p – 1}} \equiv 1\left( {{\text{mod}}\,p} \right)\) **R1**

\(x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)\) **AG**

**[3 marks]**

\(x \equiv {5^{11}} \times 7\left( {{\text{mod}}\,13} \right)\) **(M1)**

\( \equiv 341796875\left( {{\text{mod}}\,13} \right)\) **(****A1)**

**Note:** Accept equivalent calculation *eg*, using \({5^2} \equiv – 1\,{\text{mod}}\,13\).

\( \equiv 4\left( {{\text{mod}}\,13} \right)\) **A1**

**[3 marks]**

## Examiners report

[N/A]

[N/A]

[N/A]

## Question

One version of Fermat’s little theorem states that, under certain conditions, \({a^{p – 1}} \equiv 1(\bmod p)\) .

(i) Show that this result is not true when *a* = 2, *p* = 9 and state which of the conditions is not satisfied.

(ii) Find the smallest positive value of *k* satisfying the congruence \({2^{45}} \equiv k(\bmod 9)\) .

Find all the integers between 100 and 200 satisfying the simultaneous congruences \(3x \equiv 4(\bmod 5)\) and \(5x \equiv 6(\bmod 7)\) .

**Answer/Explanation**

## Markscheme

(i) \({2^8} = 256 \equiv 4(\bmod 9)\) (so not true) *A1*

9 is not prime *A1*

* *

(ii) consider various powers of 2, *e.g.* obtaining *M1*

\({2^6} = 64 \equiv 1(\bmod 9)\) *A1*

therefore

\({2^{45}} = {({2^6})^7} \times {2^3}\) *M1*

\( \equiv 8(\bmod 9){\text{ (so }}k = 8)\) *A1*

*[6 marks]*

**EITHER**

the solutions to \(3x \equiv 4(\bmod 5)\) are 3, 8, 13, 18, 23,… *M1A1*

the solutions to \(5x \equiv 6(\bmod 7)\) are 4, 11, 18,… *A1*

18 is therefore the smallest solution *A1*

the general solution is

\(18 + 35n{\text{ , }}n \in \mathbb{Z}\) *M1*

the required solutions are therefore 123, 158, 193 *A1*

**OR**

\(3x \equiv 4(\bmod 5) \Rightarrow 2 \times 3x \equiv 2 \times 4(\bmod 5) \Rightarrow x \equiv 3(\bmod 5)\) *A1*

\( \Rightarrow x = 3 + 5t\) *M1*

\( \Rightarrow 15 + 25t \equiv 6(\bmod 7) \Rightarrow 4t \equiv 5(\bmod 7) \Rightarrow 2 \times 4t \equiv 2 \times 5(\bmod 7) \Rightarrow t \equiv 3(\bmod 7)\) *A1*

\( \Rightarrow t = 3 + 7n\) *A1*

\( \Rightarrow x = 3 + 5(3 + 7n) = 18 + 35n\) *M1*

the required solutions are therefore 123, 158, 193 *A1*

**OR**

using the Chinese remainder theorem formula method

first convert the congruences to \(x \equiv 3(\bmod 5)\) and \(x \equiv 4(\bmod 7)\) *A1A1*

\(M = 35{\text{, }}{M_1} = 7{\text{, }}{M_2} = 5{\text{, }}{m_1} = 5,{\text{ }}{m_2} = 7,{\text{ }}{a_1} = 3,{\text{ }}{a_2} = 4\)

\({x_1}\) is the solution of \({M_2}{x_2} \equiv 1(\bmod {m_1})\) , *i.e.* \(7{x_1} \equiv 1(\bmod 5)\) so \({x_1} = 3\)

\({x_2}\) is the solution of \({M_2}{x_2} \equiv 1(\bmod {m_2})\) , *i.e.* \(5{x_2} \equiv 1(\bmod 7)\) so \({x_2} = 3\)

a solution is therefore

\(x = {a_1}{M_1}{x_1} + {a_2}{M_2}{x_2}\) *M1*

\( = 3 \times 7 \times 3 + 4 \times 5 \times 3 = 123\) *A1*

the general solution is \(123 + 35n\) , \(n \in \mathbb{Z}\) *M1*

the required solutions are therefore 123, 158, 193 *A1*

*[6 marks]*

## Examiners report

[N/A]

[N/A]