| Exam Board | Edexcel |
|---|---|
| Module | FP2 (Further Pure Mathematics 2) |
| Year | 2022 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Number Theory |
| Type | Euclidean algorithm with applications |
| Difficulty | Standard +0.8 This is a standard Further Maths question on the Euclidean algorithm and linear Diophantine equations. Part (a) is routine application of the algorithm, part (b) requires back-substitution to find a particular solution then scaling, and part (c) applies modular arithmetic. While multi-step, these are well-practiced techniques in FP2 with no novel insight required, making it moderately above average difficulty. |
| Spec | 8.02d Division algorithm: a = bq + r uniquely8.02f Single linear congruences: solve ax = b (mod n) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(124 = 17 \times 7 + 5\), \(17 = 3 \times 5 + 2\), \(5 = 2 \times 2 + 1\), \(\{2 = 2 \times 1\}\) | M1 | Complete attempt at Euclidean algorithm to find gcd of 124 and 17; condone numerical slip |
| Since the gcd is 1, 124 and 17 are relatively prime (coprime) | A1 | Fully correct application and conclusion that gcd/hcf = 1, therefore relatively prime |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(1 = 5 - 2 \times 2\); \(1 = 5 - 2(17 - 3 \times 5) \Rightarrow 1 = 7 \times 5 - 2 \times 17\); \(1 = 7(124 - 17 \times 7) - 2 \times 17\); \(\Rightarrow 1 = 7 \times 124 - 51 \times 17\) | M1 | Attempts Bezout's identity; condone sign slips |
| Correct Bezout's identity | A1 | |
| \(\Rightarrow 10 = 70 \times 124 - 510 \times 17\); \(x = 70, y = -510\) | A1 | Deduces correct values of \(x\) and \(y\) |
| Alternative: \(\Rightarrow 10 = 2 \times 124 - 14 \times 17\); \(x = 2, y = -14\) OR \(\Rightarrow 10 = 110 \times 17 - 15 \times 124\); \(x = -15, y = 110\) | M1, A1, A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Complete method using modulo arithmetic to achieve \(x \equiv \ldots \pmod{17}\); e.g. \(7 \times 124x \equiv 7 \times 6 \pmod{17} \Rightarrow x \equiv \ldots \pmod{17}\) | M1 | Multiplies by multiplicative inverse of 124; or uses Bezout's identity from (b) |
| \(x \equiv 8 \pmod{17}\) | A1 |
## Question 4:
### Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $124 = 17 \times 7 + 5$, $17 = 3 \times 5 + 2$, $5 = 2 \times 2 + 1$, $\{2 = 2 \times 1\}$ | M1 | Complete attempt at Euclidean algorithm to find gcd of 124 and 17; condone numerical slip |
| Since the gcd is 1, 124 and 17 are relatively prime (coprime) | A1 | Fully correct application and conclusion that gcd/hcf = 1, therefore relatively prime |
### Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $1 = 5 - 2 \times 2$; $1 = 5 - 2(17 - 3 \times 5) \Rightarrow 1 = 7 \times 5 - 2 \times 17$; $1 = 7(124 - 17 \times 7) - 2 \times 17$; $\Rightarrow 1 = 7 \times 124 - 51 \times 17$ | M1 | Attempts Bezout's identity; condone sign slips |
| Correct Bezout's identity | A1 | |
| $\Rightarrow 10 = 70 \times 124 - 510 \times 17$; $x = 70, y = -510$ | A1 | Deduces correct values of $x$ and $y$ |
| **Alternative:** $\Rightarrow 10 = 2 \times 124 - 14 \times 17$; $x = 2, y = -14$ OR $\Rightarrow 10 = 110 \times 17 - 15 \times 124$; $x = -15, y = 110$ | M1, A1, A1 | |
### Part (c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Complete method using modulo arithmetic to achieve $x \equiv \ldots \pmod{17}$; e.g. $7 \times 124x \equiv 7 \times 6 \pmod{17} \Rightarrow x \equiv \ldots \pmod{17}$ | M1 | Multiplies by multiplicative inverse of 124; or uses Bezout's identity from (b) |
| $x \equiv 8 \pmod{17}$ | A1 | |
---\begin{enumerate}
\item (a) Use the Euclidean algorithm to show that 124 and 17 are relatively prime (coprime).\\
(b) Hence solve the equation
\end{enumerate}
$$124 x + 17 y = 10$$
(c) Solve the congruence equation
$$124 x \equiv 6 \bmod 17$$
\hfill \mbox{\textit{Edexcel FP2 2022 Q4 [7]}}