A2 October 2021 Q4
4. Let \(G\) be a group of order \(46^{46} + 47^{47}\)
Using Fermat’s Little Theorem and explaining your reasoning, determine which of the following are possible orders for a subgroup of \(G\)
(7)
| Scheme | Marks | AO |
|---|---|---|
| (Order of a subgroup must divide the order of a group by Lagrange’s Theorem), so need to check if 11 (and/or 21) divides \(46^{46} + 47^{47}\) and by FLT, e.g. \(a^{11-1} = a^{10} \equiv 1 \pmod{11}\), so | M1 | 1.1b |
| \(46^{46} + 47^{47} \equiv 2^{4 \times 10 + 6} + 3^{4 \times 10 + 7} \equiv 2^6 + 3^7 \equiv 64 + (3^3)^2 \times 3\) \(\equiv 9 + 5^2 \times 3 \equiv 84 \equiv 7 \pmod{11}\) | M1 | 3.1a |
| Hence 11 is not a divisor of \(46^{46} + 47^{47}\) so not a possible order for a subgroup. | A1 | 2.2a |
Notes
M1: For an attempt to apply a correct Fermat’s Little theorem at least once in the question with either \(p = 11\), \(p = 7\) or \(p = 3\) on either the \(46^{46}\) or \(47^{47}\) term.
M1: Applies FLT and congruence arithmetic fully to find the residue of \(46^{46} + 47^{47}\) modulo 11. There will be lots of different routes, so look for an attempt to apply FLT that leads to determining if 11 is a divisor or not.
A1: \(46^{46} + 47^{47} \equiv 7 \pmod{11}\) (accept equivalents as long as it is clear it is not congruent to 0) and deduces it is not a possible order for a subgroup.
| Scheme | Marks | AO |
|---|---|---|
| \(21 = 7 \times 3\) so need to check for factors of 7 and 3, using \(a^2 \equiv 1 \pmod{3}\) and \(a^6 \equiv 1 \pmod{7}\) | M1 | 3.1a |
| \(46^{46} + 47^{47} \equiv 1^{46} + 2^{47} \equiv 1 + 2^{2 \times 23 + 1} \equiv 1 + 2^1 \equiv 3 \equiv 0 \pmod{3}\) | M1 | 1.1b |
| \(46^{46} + 47^{47} \equiv 4^{46} + (-2)^{47} \equiv 4^{6 \times 7 + 4} + (-2)^{6 \times 7 + 5} \equiv 4^4 + (-2)^5\) \(\equiv 16^2 - 32 \equiv 9^2 - 4 \equiv 81 - 4 \equiv 77 \equiv 0 \pmod{7}\) | M1 | 2.1 |
| As \(46^{46} + 47^{47}\) divisible by both 3 and 7 it is divisible by 21 and hence this is a possible order for a subgroup. | A1 | 2.4 |
| (7) | ||
| (7 marks) |
Notes
M1: Applies checks for both 7 and 3 as divisors of \(46^{46} + 47^{47}\) via similar strategy.
M1: Applies FLT with \(p = 3\) to find a smaller residue modulo 3. Other routes are possible.
M1: Applies FLT with \(p = 7\) to find a smaller residue modulo 7. Other routes are possible.
A1: Shows \(46^{46} + 47^{47}\) congruent to 0 modulo 3 and modulo 7, and deduces 21 divides \(46^{46} + 47^{47}\) hence it is a possible order for a subgroup.
Alt:
M1: Reduces the bases modulo 21 and applies a power reduction technique using congruences for at least one of the power of 46 or 47
M1: Reduces fully by congruence arithmetic either the \(46^{46}\) or \(47^{47}\) term.
M1: Reduces fully by congruence arithmetic both the \(46^{46}\) and \(47^{47}\) terms
A1: Shows \(46^{46} + 47^{47}\) congruent to 0 modulo 21, and deduces 21 divides \(46^{46} + 47^{47}\) hence it is a possible order for a subgroup.