| Exam Board | OCR |
|---|---|
| Module | Further Additional Pure (Further Additional Pure) |
| Year | 2018 |
| Session | December |
| Marks | 9 |
| Topic | Number Theory |
| Type | Fermat's Little Theorem |
| Difficulty | Challenging +1.8 This is a Further Maths question requiring systematic application of modular arithmetic and Fermat's Little Theorem. Part (a) is straightforward computation, part (b) requires finding a modular inverse (extended Euclidean algorithm or inspection), and part (c) demands understanding of order and systematic calculation of powers mod 47. While conceptually accessible to Further Maths students, it requires careful multi-step reasoning and computational accuracy across all parts, placing it well above average difficulty. |
| Spec | 8.02e Finite (modular) arithmetic: integers modulo n8.02f Single linear congruences: solve ax = b (mod n)8.02l Fermat's little theorem: both forms |
| Answer | Marks | Guidance |
|---|---|---|
| \(10^2 = 100 = 2 \times 47 + 6\) | M1 | 1.1 |
| so \(10^2 \equiv 6 \pmod{47}\) | A1 | 2.4 |
| Total: [2] | Attempted division of 100 by 47; AG Result shown with justification |
| Answer | Marks | Guidance |
|---|---|---|
| \(6 \times 8 = 48 = 47 + 1 \equiv 1 \pmod{47}\) | E1 | 2.1 |
| so \(r = 8\) is the required reciprocal of 6 modulo 47 | B1 | 2.2a |
| Total: [2] | Correct result clearly demonstrated; Correct reciprocal identified, possibly BC |
| Answer | Marks | Guidance |
|---|---|---|
| \(10^{46} \equiv 1 \pmod{47}\) | B1 | 3.1a |
| since 47 is prime and hcf(10, 47) = 1 | E1 | 2.4 |
| The order of 10 mod 47 is then a factor of 46 | M1 | 2.1 |
| and since \(10^{46} - 1 = (10^{23} - 1)(10^{23} + 1), 10^{23} \pm 1\) and \(n = 23\) | A1 | 3.2a |
| The only possible smaller divisor of 46 is 2, but (i) showed that \(10^2\) invalid | B1 | 2.3 |
| Total: [5] | Answer must be justified, not just claimed |
**Part (a)**
| $10^2 = 100 = 2 \times 47 + 6$ | M1 | 1.1 |
| so $10^2 \equiv 6 \pmod{47}$ | A1 | 2.4 |
| Total: [2] | Attempted division of 100 by 47; AG Result shown with justification | |
**Part (b)**
| $6 \times 8 = 48 = 47 + 1 \equiv 1 \pmod{47}$ | E1 | 2.1 |
| so $r = 8$ is the required reciprocal of 6 modulo 47 | B1 | 2.2a |
| Total: [2] | Correct result clearly demonstrated; Correct reciprocal identified, possibly BC | |
**Part (c)**
| $10^{46} \equiv 1 \pmod{47}$ | B1 | 3.1a |
| since 47 is prime and hcf(10, 47) = 1 | E1 | 2.4 |
| The order of 10 mod 47 is then a factor of 46 | M1 | 2.1 |
| and since $10^{46} - 1 = (10^{23} - 1)(10^{23} + 1), 10^{23} \pm 1$ and $n = 23$ | A1 | 3.2a |
| The only possible smaller divisor of 46 is 2, but (i) showed that $10^2$ invalid | B1 | 2.3 |
| Total: [5] | Answer must be justified, not just claimed | |3
\begin{enumerate}[label=(\alph*)]
\item Show that $10 ^ { 2 } \equiv 6 ( \bmod 47 )$.
\item Determine the integer $r$, with $0 < r < 47$, such that $6 r \equiv 1 ( \bmod 47 )$.
\item Determine the least positive integer $n$ for which $10 ^ { n } \equiv 1$ or $- 1 ( \bmod 47 )$.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Additional Pure 2018 Q3 [9]}}