AS June 2025 Q1
1.
In this question you must show all stages of your working.
Solutions based entirely on calculator technology are not acceptable.
(i)
(a) Use the Euclidean algorithm to determine the highest common factor \(h\) of 105 and 24 (3)
(b) Hence determine integers \(a\) and \(b\) such that\[105a + 24b = h\] (3)
(ii) Determine the remainder when \(179^5\) is divided by 11 (2)
| Scheme | Marks | AO |
|---|---|---|
| \(105 = 4 \times 24 + 9\) | M1 | 1.1b |
| \(24 = 2 \times 9 + 6, \quad 9 = 1 \times 6 + 3, \quad 6 = 2 \times 3 + 0\) | M1 | 1.1b |
| \(h = 3\) | A1 | 2.2a |
| (3) |
Notes
M1: Starts the Euclidean algorithm to obtain \(105 = p \times 24 + q\)
M1: Completes the algorithm correctly to obtain a zero remainder.
A1: All correct and concludes \(h = 3\)
| Scheme | Marks | AO |
|---|---|---|
| \(3 = 9 - 1 \times 6\) | M1 | 1.1b |
| \(= 9 - 1 \times (24 - 2 \times 9) = 3 \times 9 - 1 \times 24\) \(= 3(105 - 4 \times 24) - 1 \times 24\) | M1 | 1.1b |
| \(= 3 \times 105 - 13 \times 24\) \((a = 3,\ b = -13)\) | A1 | 1.1b |
| (3) |
Notes
M1: Begins the progress of back substitution.
M1: Completes the process.
A1: Correct expression or correct values.
| Scheme | Marks | AO |
|---|---|---|
| \(179 = 16 \times 11 + 3\) \(\Rightarrow 179 \equiv 3 \pmod{11}\) \(179^5 \equiv 3^5 \pmod{11} \equiv 243 \pmod{11}\) \(243 = 22 \times 11 + 1\) | M1 | 1.1b |
| \(179^5 \equiv 1 \pmod{11}\) so the remainder is 1 | A1 | 2.2a |
| (2) | ||
| (8 marks) |
Notes
M1: Attempts the remainder when 179 is divided by 11 and makes progress in establishing the remainder when \(179^5\) is divided by 11
A1: Obtains the remainder 1