Question nov 2019
Question
In parts (b) and (c), $(a b c \ldots)_n$ denotes the number $a b c \ldots$ written in base $n$, where $n \in \mathrm{Z}^{+}$. For example, $(359)_n=3 n^2+5 n+9$.
a.i. State Fermat’s little theorem.
[2]
a.ii. Find the remainder when $15^{1207}$ is divided by 13 .
[5]
b. Convert $(7 A 2)_{16}$ to base 5 , where $(A)_{16}=(10)_{10}$.
c. Consider the equation $(1251)_n+(30)_n=(504)_n+(504)_n$.
Find the value of $n$.
▶️Answer/Explanation
Markscheme
a.i. EITHER
$$
a^p \equiv a(\bmod p) \quad \boldsymbol{A 1}
$$
where $p$ is prime
A1
OR
$$
a^{p-1} \equiv 1(\bmod p) \quad \boldsymbol{A 1}
$$
where $p$ is prime and $p$ does not divide $a$ (or equivalent statement)
A1
[2 marks]
$$
\begin{aligned}
& \text { a.ii. } 15^{1207} \equiv 2^{1207}(\bmod 13) \\
& 2^{12} \equiv 1(\bmod 13) \quad(\text { M1)(A1) } \\
& 2^{1207}=\left(2^{12}\right)^{100} 2^7 \quad \text { (M1) } \\
& 2^{1207}\left(\equiv 2^7\right) \equiv 11(\bmod 13)
\end{aligned}
$$
(M1)
(M1)A1
the remainder is 11
Note: Award as above for using 15 instead of 2 .
[5 marks]
b. $(7 A 2)_{16}=7 \times 16^2+10 \times 16+2 \quad$ M1
$$
=1954
$$
A1
EITHER
$$
5 \text { \1954 } \begin{array}{r}
390 r 4 \\
78 r 0 \\
15 r 3 \\
3 r 0 \\
0 r 3
\end{array}
$$
OR
$$
1954=3 \times 5^4+0 \times 5^3+3 \times 5^2+0 \times 5^1+4 \quad \text { M1 }
$$
THEN
$$
(7 A 2)_{16}=(30304)_5 \quad \text { A1 }
$$
[4 marks]
c. the equation can be written as
$$
\begin{aligned}
& n^3+2 n^2+5 n+1+3 n=2\left(5 n^2+4\right) \quad \text { M1A1 } \\
& \Rightarrow n^3-8 n^2+8 n-7=0 \quad \text { (M1) }
\end{aligned}
$$
Note: The (M1) is for an attempt to solve the original equation.
$$
\begin{aligned}
& n=7 \\
& {[4 \text { marks }]}
\end{aligned}
$$
[4 marks]
Question
a.(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.\][11]
b.Show that \({x^{97}} – x + 1 \equiv 0(\bmod 97)\) has no solution.[3]
▶️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
a.Write 57128 as a product of primes.[4]
c.Prove that \(\left. {22} \right|{5^{11}} + {17^{11}}\).[4]
▶️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
a.Show that a positive integer, written in base 10, is divisible by 9 if the sum of its digits is divisible by 9.[7]
b.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}\) .[9]
▶️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
(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 A1 for the congruence.
[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
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
a.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)\) .[6]
b.Find all the integers between 100 and 200 satisfying the simultaneous congruences \(3x \equiv 4(\bmod 5)\) and \(5x \equiv 6(\bmod 7)\) .[6]
▶️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]