| Exam Board | Edexcel |
|---|---|
| Module | FP2 (Further Pure Mathematics 2) |
| Year | 2021 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Number Theory |
| Type | Euclidean algorithm with applications |
| Difficulty | Standard +0.3 This is a straightforward application of the Euclidean algorithm followed by routine modular arithmetic. Part (a) is a standard textbook exercise in finding Bézout coefficients, part (b) requires recognizing that b is the inverse, and part (c) is simple multiplication. The question is entirely procedural with no novel insight required, making it slightly easier than average for Further Maths. |
| Spec | 8.02d Division algorithm: a = bq + r uniquely8.02e Finite (modular) arithmetic: integers modulo n8.02f Single linear congruences: solve ax = b (mod n) |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| \(125 = 87 \times 1 + 38\), \(87 = 38 \times 2 + 11...\) | M1 | Begins Euclidean algorithm, attempt at first two steps. Allow slips. |
| \(38 = 11 \times 3 + 5\), \(11 = 5 \times 2 + 1\) | M1, A1 | Completes process to stage shown (at least three steps to reach \(+1\)); algorithm correctly carried out |
| \(1 = 11 - 5 \times 2 = 11-(38-11\times3)\times2 = 11\times7-38\times2 = (87-38\times2)\times7-38\times2 = 87\times7-38\times16\) | M1 | Starts back substitution – at least two substitutions made |
| \(1 = 87\times7-(125-87\times1)\times16 = -16\times125+23\times87\), so \(a=-16\), \(b=23\) | A1 | Completes process and finds correct values for \(a\) and \(b\) |
| (5) |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| From (a) \(23\times87\equiv1\pmod{125}\) so multiplicative inverse of 87 is 23 | B1ft | Deduces correct multiplicative inverse. Accept 23 or anything congruent to 23 mod 125, or follow through on their \(b\) |
| (1) |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| \(x \equiv 23\times16\pmod{125}\) | M1 | Multiplies 16 by their multiplicative inverse, or any other full method |
| \(x \equiv 368 \equiv 118\pmod{125}\) | A1 | Accept 118 or anything congruent to 118 mod 125 as part of a correct modulo statement. Do not accept just 368 on its own. |
| (2) |
# Question 3:
## Part (a):
| Working | Mark | Guidance |
|---------|------|----------|
| $125 = 87 \times 1 + 38$, $87 = 38 \times 2 + 11...$ | **M1** | Begins Euclidean algorithm, attempt at first two steps. Allow slips. |
| $38 = 11 \times 3 + 5$, $11 = 5 \times 2 + 1$ | **M1, A1** | Completes process to stage shown (at least three steps to reach $+1$); algorithm correctly carried out |
| $1 = 11 - 5 \times 2 = 11-(38-11\times3)\times2 = 11\times7-38\times2 = (87-38\times2)\times7-38\times2 = 87\times7-38\times16$ | **M1** | Starts back substitution – at least two substitutions made |
| $1 = 87\times7-(125-87\times1)\times16 = -16\times125+23\times87$, so $a=-16$, $b=23$ | **A1** | Completes process and finds correct values for $a$ and $b$ |
| | **(5)** | |
## Part (b):
| Working | Mark | Guidance |
|---------|------|----------|
| From (a) $23\times87\equiv1\pmod{125}$ so multiplicative inverse of 87 is 23 | **B1ft** | Deduces correct multiplicative inverse. Accept 23 or anything congruent to 23 mod 125, or follow through on their $b$ |
| | **(1)** | |
## Part (c):
| Working | Mark | Guidance |
|---------|------|----------|
| $x \equiv 23\times16\pmod{125}$ | **M1** | Multiplies 16 by their multiplicative inverse, or any other full method |
| $x \equiv 368 \equiv 118\pmod{125}$ | **A1** | Accept 118 or anything congruent to 118 mod 125 as part of a correct modulo statement. Do not accept just 368 on its own. |
| | **(2)** | |
---\begin{enumerate}
\item (a) Use the Euclidean Algorithm to find integers $a$ and $b$ such that
\end{enumerate}
$$125 a + 87 b = 1$$
(b) Hence write down a multiplicative inverse of 87 modulo 125\\
(c) Solve the linear congruence
$$87 x \equiv 16 ( \bmod 125 )$$
\hfill \mbox{\textit{Edexcel FP2 2021 Q3 [8]}}