| Exam Board | OCR |
|---|---|
| Module | Further Additional Pure (Further Additional Pure) |
| Year | 2018 |
| Session | March |
| Marks | 12 |
| Topic | Number Theory |
| Type | Quadratic residues |
| Difficulty | Hard +2.3 This is a Further Maths question requiring sophisticated number theory: part (i)(a) is routine, but (i)(b) requires modular arithmetic insight to eliminate solutions, and part (ii) demands knowledge of Fermat's Little Theorem applied to multiple primes to show divisibility of 11^12 - 1, which is non-standard and requires extended reasoning across several cases. |
| Spec | 8.02a Number bases: conversion and arithmetic in base n8.02b Divisibility tests: standard tests for 2, 3, 4, 5, 8, 9, 118.02d Division algorithm: a = bq + r uniquely8.02e Finite (modular) arithmetic: integers modulo n8.02g Quadratic residues: calculate and solve equations involving them8.02l Fermat's little theorem: both forms |
| Answer | Marks | Guidance |
|---|---|---|
| 1, 4, 9, 5, 3 | B1, B1 [2] | Give 1st B1 for any 3 correct; 2nd B1 for all 5 and allow 0, no incorrect extras condone (0,1), 4, 9, 5, 3, 3, 5, 9, 4, 1 |
| Answer | Marks | Guidance |
|---|---|---|
| The 5th-powers (mod 11) are 0, 1, 10 so LHS = 0, 1, 10 (mod 11); 2017 ≡ 4 (mod 11) so RHS = 4, 5, 8, 2, 9, 7 (mod 11). Since LHS and RHS are not equal modulo 11, the equation has no solution in integers | M1, A1, M1, A1, E1 [5] | Looking at 5th powers mod 11; All 3 found with no extras; 2017 = 4 (mod 11) BC; FT each of (a)'s residues + 4; Must follow from fully correct working |
| Answer | Marks | Guidance |
|---|---|---|
| mod 9, \(M \equiv 2^{12} - 1 = (2^4)^3 - 1 = (-1)^3 - 1 = -1 - 1 = 0\) OR \(11^{12} - 1 = (11^6 - 1)(11^6 + 1) = (11^3 - 1)(11^3 + 1)(11^6 + 1)\) and \(11^3 + 1 = 1332\), which is divisible by 9 using the standard divisibility test | B1 | Using the *difference-of-two-squares* factorisation (e.g.) |
| mod 5, \(M \equiv 1^{12} - 1 = 0\) or via above factorisation, noting that \(5 \mid 11^3 - 1 = 1330\) | B1 | NB: can argue via \(10 \mid (11^n - 1) \forall\) integers \(n \in \mathbb{N}\) by the *Factor Theorem*; etc. |
| The factor \(11^6 - 1 \equiv 0 \pmod{7}\) by FLT since \(\gcd(11, 7) = 1\) and 7 is prime | B1 | |
| \(M \equiv 11^{12} - 1 \equiv 0 \pmod{13}\) by FLT since \(\gcd(11, 13) = 1\) and 13 is prime | B1 | |
| mod 61, \(11^2 = 121 \equiv -1 \Rightarrow 11^{12} - 1 \equiv (-1)^6 - 1 = 1 - 1 = 0\) | B1 | Any reasonable, clearly explained method is acceptable |
| [5] | ||
| NB \(M = 11^{12} - 1 = 3 \, 138 \, 428 \, 376 \, 720 = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13 \cdot 19 \cdot 37 \cdot 61 \cdot 1117\) (Also, \(M\) has \(11^3 + 1\) as a factor, and \(11^3 + 1 = (11 + 1)(11^2 - 11 \cdot 1 + 1^2) = 12 \times 111 = 3 \times 37\); that is, \(M\) is divisible by \(11^2 - 11 \cdot 1 + 1^2 = 111 = 3 \times 37\)) | NB FLT is *Fermat's Little Theorem* |
## (i) (a)
| 1, 4, 9, 5, 3 | B1, B1 [2] | Give 1st B1 for any 3 correct; 2nd B1 for all 5 and allow 0, no incorrect extras condone (0,1), 4, 9, 5, 3, 3, 5, 9, 4, 1 |
## (i) (b)
| The 5th-powers (mod 11) are 0, 1, 10 so LHS = 0, 1, 10 (mod 11); 2017 ≡ 4 (mod 11) so RHS = 4, 5, 8, 2, 9, 7 (mod 11). Since LHS and RHS are not equal modulo 11, the equation has no solution in integers | M1, A1, M1, A1, E1 [5] | Looking at 5th powers mod 11; All 3 found with no extras; 2017 = 4 (mod 11) BC; FT each of (a)'s residues + 4; Must follow from fully correct working |
## (ii) DR
| **mod 9,** $M \equiv 2^{12} - 1 = (2^4)^3 - 1 = (-1)^3 - 1 = -1 - 1 = 0$ **OR** $11^{12} - 1 = (11^6 - 1)(11^6 + 1) = (11^3 - 1)(11^3 + 1)(11^6 + 1)$ and $11^3 + 1 = 1332$, which is divisible by 9 using the standard divisibility test | B1 | Using the *difference-of-two-squares* factorisation (e.g.) |
| **mod 5,** $M \equiv 1^{12} - 1 = 0$ or via above factorisation, noting that $5 \mid 11^3 - 1 = 1330$ | B1 | NB: can argue via $10 \mid (11^n - 1) \forall$ integers $n \in \mathbb{N}$ by the *Factor Theorem*; etc. |
| The factor $11^6 - 1 \equiv 0 \pmod{7}$ by FLT since $\gcd(11, 7) = 1$ and 7 is prime | B1 | |
| $M \equiv 11^{12} - 1 \equiv 0 \pmod{13}$ by FLT since $\gcd(11, 13) = 1$ and 13 is prime | B1 | |
| **mod 61,** $11^2 = 121 \equiv -1 \Rightarrow 11^{12} - 1 \equiv (-1)^6 - 1 = 1 - 1 = 0$ | B1 | Any reasonable, clearly explained method is acceptable |
| [5] | | |
| **NB** $M = 11^{12} - 1 = 3 \, 138 \, 428 \, 376 \, 720 = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13 \cdot 19 \cdot 37 \cdot 61 \cdot 1117$ (Also, $M$ has $11^3 + 1$ as a factor, and $11^3 + 1 = (11 + 1)(11^2 - 11 \cdot 1 + 1^2) = 12 \times 111 = 3 \times 37$; that is, $M$ is divisible by $11^2 - 11 \cdot 1 + 1^2 = 111 = 3 \times 37$) | | NB FLT is *Fermat's Little Theorem* |
---4
\begin{enumerate}[label=(\roman*)]
\item (a) Find all the quadratic residues modulo 11.\\
(b) Prove that the equation $y ^ { 5 } = x ^ { 2 } + 2017$ has no solution in integers $x$ and $y$.
\item In this question you must show detailed reasoning.
The numbers $M$ and $N$ are given by
$$M = 11 ^ { 12 } - 1 \text { and } N = 3 ^ { 2 } \times 5 \times 7 \times 13 \times 61$$
Prove that $M$ is divisible by $N$.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Additional Pure 2018 Q4 [12]}}