A2 June 2024 Q1
1.
In this question you must show detailed reasoning.
Use Fermat’s Little Theorem to determine the least positive residue of\[21^{80} \pmod{23}\]
| Scheme | Marks | AO |
|---|---|---|
| \(21^{22} \equiv 1 \pmod{23}\) or \(21^{23} \equiv 21 \pmod{23}\) or \(21^{23} \equiv -2 \pmod{23}\) | B1 | 1.2 |
| \(80 = 3 \times 22 + 14 \Rightarrow 21^{80} \equiv 21^{14} \pmod{23}\) \(80 = 3 \times 23 + 11 \Rightarrow 21^{80} \equiv -8 \times 21^{11} \pmod{23}\) | M1 | 1.1b |
| For example \(\equiv \left((-2)^4\right)^3 \times (-2)^2 \equiv 16^3 \times 4 \equiv (-7)^2 \times -7 \times 4 \equiv 49 \times -28 \equiv 3 \times 18 \equiv 54\) \(\equiv (-2)^{14} \pmod{23} \equiv 16384 \pmod{23}\) \(\equiv (-2)^{14} \equiv (4)^7 \pmod{23}\) \(\equiv \left((-2)^4\right)^3 \times (-2)^2 \equiv 16^3 \times 4 \equiv \{16384\}\) \(21^2 = 441 \equiv 4 \pmod{23} \Rightarrow \left(21^2\right)^7 = (4)^7 = \{16384\}\) \((3 \times 7)^{14} = 3^{14} \times 7^{14} = 3^{14} \times (49)^7 \equiv 4 \times (3)^7 \pmod{23} \equiv 4 \times 2 \pmod{23}\) \(\equiv -8 \times (-2)^{11} \equiv 16 \times 2^{10}\) Leading to \(\equiv \ldots \pmod{23}\) | dM1 | 1.1b |
| \(\equiv 8 \pmod{23}\) | A1 | 2.2a |
| (4) | ||
| (4 marks) |
Notes
B1: Accurately recalls Fermat’s Little Theorem. Allow if stated correctly in general form, \(a^{p-1} \equiv 1 \pmod{p}\). May be implied.
M1: Attempts to write the index in a suitable form and then applies the theorem, look for \(80 = 22k + r\) or equivalent leading to a reduced index.
dM1: For a full method to reduce to a least residue. There are many ways that they can split up their value, including use of a calculator to work with a higher power as long as an attempt at FLT to reduce initially has been seen. Condone a sign slip e.g using \(21^2 \equiv 19 \pmod{23}\) instead of \(21^2 \equiv -19 \pmod{23}\) as long as there is a complete method and there is only one sign slip
A1: Correct answer.