| Exam Board | OCR |
|---|---|
| Module | Further Additional Pure (Further Additional Pure) |
| Year | 2018 |
| Session | September |
| Marks | 11 |
| Topic | Number Theory |
| Type | Wilson's Theorem |
| Difficulty | Hard +2.3 This is a challenging Further Maths question requiring proof techniques in modular arithmetic and combinatorics. Part (i) demands insight into manipulating binomial coefficients modulo a prime using Wilson's theorem. Part (ii) extends this to a more complex binomial coefficient requiring sophisticated algebraic manipulation and understanding of prime properties. The 11-mark allocation and proof-based nature place this well above typical A-level questions. |
| Spec | 8.02l Fermat's little theorem: both forms8.02o Binomial theorem: (a+b)^p = a^p + b^p (mod p) for prime p |
| Answer | Marks | Guidance |
|---|---|---|
| (i) \(N = \begin{pmatrix} p-1 \\ r \end{pmatrix} = \frac{(p-1)!}{r!(p-r-1)!}\) so \(r! N = (p-1)(p-2) \ldots (p-r)\) | M1, A1 | Use of correct factorial form for \(N\); Correct with all fractions removed |
| \(\equiv (-1)(-2) \ldots (-r) \pmod{p}\) | M1 | |
| \(= (-1)^r (r!)\) | A1 | |
| Since all terms in \(r!\) are \(< p\), \(\gcd(r!, p) = 1\) so we can divide both sides by \(r!\) to obtain \(N \equiv (-1)^r \pmod{p}\) | A1 | AG obtained with full justification |
| (ii) \(M = \begin{pmatrix} 2p \\ p \end{pmatrix} = \frac{(2p)!}{p! \, p!} \Rightarrow p! M = (2p)(2p-1)(2p-2) \ldots (2p-(p-1))\) | M1, A1 | Use of correct factorial form for \(M\); Correct with all fractions removed |
| \(\Rightarrow (p-1)! M = 2(2p-1)(2p-2) \ldots (2p-(p-1))\) | M1 | |
| \(\equiv 2(−1)(−2) \ldots (−(p-1)) \pmod{p}\) | M1 | |
| \(= 2(−1)^{p-1}(p-1)!\) | A1 | |
| Since all terms in \((p-1)!\) are \(< p\), \(\gcd((p-1)!, p) = 1\) we can divide both sides by \((p-1)!\); also \((p-1)\) is even so \((-1)^{p-1} = 1\). Hence \(M \equiv 2 \pmod{p}\) | A1 | AG obtained with full justification |
**(i)** $N = \begin{pmatrix} p-1 \\ r \end{pmatrix} = \frac{(p-1)!}{r!(p-r-1)!}$ so $r! N = (p-1)(p-2) \ldots (p-r)$ | M1, A1 | Use of correct factorial form for $N$; Correct with all fractions removed
$\equiv (-1)(-2) \ldots (-r) \pmod{p}$ | M1 |
$= (-1)^r (r!)$ | A1 |
Since all terms in $r!$ are $< p$, $\gcd(r!, p) = 1$ so we can divide both sides by $r!$ to obtain $N \equiv (-1)^r \pmod{p}$ | A1 | AG obtained with full justification
**(ii)** $M = \begin{pmatrix} 2p \\ p \end{pmatrix} = \frac{(2p)!}{p! \, p!} \Rightarrow p! M = (2p)(2p-1)(2p-2) \ldots (2p-(p-1))$ | M1, A1 | Use of correct factorial form for $M$; Correct with all fractions removed
$\Rightarrow (p-1)! M = 2(2p-1)(2p-2) \ldots (2p-(p-1))$ | M1 |
$\equiv 2(−1)(−2) \ldots (−(p-1)) \pmod{p}$ | M1 |
$= 2(−1)^{p-1}(p-1)!$ | A1 |
Since all terms in $(p-1)!$ are $< p$, $\gcd((p-1)!, p) = 1$ we can divide both sides by $(p-1)!$; also $(p-1)$ is even so $(-1)^{p-1} = 1$. Hence $M \equiv 2 \pmod{p}$ | A1 | AG obtained with full justification\begin{enumerate}[label=(\roman*)]
\item You are given that $N = \binom{p-1}{r}$, where $p$ is a prime number and $r$ is an integer such that $1 \leq r \leq p - 1$.
By considering the number $N \times r!$, prove that $N \equiv (-1)^r \pmod{p}$. [5]
\item You are given that $M = \binom{2p}{p}$, where $p$ is an odd prime number. Prove that $M \equiv 2 \pmod{p}$. [6]
\end{enumerate}
\hfill \mbox{\textit{OCR Further Additional Pure 2018 Q5 [11]}}