| Exam Board | Edexcel |
|---|---|
| Module | FP2 AS (Further Pure 2 AS) |
| Year | 2022 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Number Theory |
| Type | Euclidean algorithm with applications |
| Difficulty | Standard +0.8 This is a multi-part Further Maths question requiring systematic application of the Euclidean algorithm, back-substitution to find Bézout coefficients, modular arithmetic with linear congruences, and modular exponentiation. While each technique is standard for FP2, the combination of multiple steps, the need for careful algebraic manipulation without calculator aid, and the requirement to work through extended Euclidean algorithm back-substitution places this above average difficulty, though not exceptionally hard for Further Maths students who have practiced these algorithms. |
| Spec | 8.02d Division algorithm: a = bq + r uniquely8.02e Finite (modular) arithmetic: integers modulo n8.02i Prime numbers: composites, HCF, coprimality |
| Answer | Marks | Guidance |
|---|---|---|
| Working/Answer | Mark | Guidance |
| \(416 = 5\times72+56\) | M1 | 1.1b — starts process with \(416=p\times72+q\) |
| \(72=1\times56+16;\ 56=3\times16+8;\ 16=2\times8(+0)\) | M1 | 1.1b — continues until remainder zero |
| Hence \(h=8\) | A1 | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Working/Answer | Mark | Guidance |
| \(8=56-3\times16\) | M1 | 1.1b — begins back substitution |
| \(=56-3(72-1\times56)=4\times56-3\times72 = 4\times(416-5\times72)-3\times72\) | M1 | 1.1b — completes process |
| \(=4\times416-23\times72\) (so \(a=4\) and \(b=-23\)) | A1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Working/Answer | Mark | Guidance |
| \(23\times72=4\times416-8\equiv -8\pmod{416}\), or \(23\times72=1656\Rightarrow 1656-k\times416=\ldots\) | M1 | 3.1a |
| \(c=416-8=408\) | A1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Working/Answer | Mark | Guidance |
| E.g. \(5^{10}\equiv(5^2)^5\equiv25^5\equiv(-1)^5\pmod{13}\) | M1 | 1.1b — reduces a power of 5 using mod 13 |
| \(\equiv -1\pmod{13}\) | dM1 | 1.1b — completes to smallest residue |
| \(\equiv 12\pmod{13}\) | A1 | 2.2a |
## Question 4(i)(a):
| Working/Answer | Mark | Guidance |
|---|---|---|
| $416 = 5\times72+56$ | M1 | 1.1b — starts process with $416=p\times72+q$ |
| $72=1\times56+16;\ 56=3\times16+8;\ 16=2\times8(+0)$ | M1 | 1.1b — continues until remainder zero |
| Hence $h=8$ | A1 | 2.2a |
---
## Question 4(i)(b):
| Working/Answer | Mark | Guidance |
|---|---|---|
| $8=56-3\times16$ | M1 | 1.1b — begins back substitution |
| $=56-3(72-1\times56)=4\times56-3\times72 = 4\times(416-5\times72)-3\times72$ | M1 | 1.1b — completes process |
| $=4\times416-23\times72$ (so $a=4$ and $b=-23$) | A1 | 1.1b |
---
## Question 4(i)(c):
| Working/Answer | Mark | Guidance |
|---|---|---|
| $23\times72=4\times416-8\equiv -8\pmod{416}$, or $23\times72=1656\Rightarrow 1656-k\times416=\ldots$ | M1 | 3.1a |
| $c=416-8=408$ | A1 | 1.1b |
---
## Question 4(ii):
| Working/Answer | Mark | Guidance |
|---|---|---|
| E.g. $5^{10}\equiv(5^2)^5\equiv25^5\equiv(-1)^5\pmod{13}$ | M1 | 1.1b — reduces a power of 5 using mod 13 |
| $\equiv -1\pmod{13}$ | dM1 | 1.1b — completes to smallest residue |
| $\equiv 12\pmod{13}$ | A1 | 2.2a |
---4. In this question you must show all stages of your working. Solutions relying on calculator technology are not acceptable.
\begin{enumerate}[label=(\roman*)]
\item (a) Use the Euclidean algorithm to find the highest common factor $h$ of 416 and 72\\
(b) Hence determine integers $a$ and $b$ such that
$$416 a + 72 b = h$$
(c) Determine the value $c$ in the set $\{ 0,1,2 \ldots , 415 \}$ such that
$$23 \times 72 \equiv c ( \bmod 416 )$$
\item Evaluate $5 ^ { 10 } ( \bmod 13 )$ giving your answer as the smallest positive integer solution.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FP2 AS 2022 Q4 [11]}}