Practise › Questions › Modular arithmetic and Fermat's little theorem
Modular arithmetic and Fermat's little theorem questions
Work with remainders instead of numbers and enormous powers become manageable. Fermat's little theorem then collapses them further, in a single line.
7 original questions · 27 marks · the modular arithmetic and fermat's little theorem notes · Further Pure 2
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Find the least positive residue of 3100 modulo 7.
Worked answer
7 is prime and 3 is not a multiple of it, so Fermat gives 3⁶ ≡ 1 (mod 7). Reducing the exponent: 100 = 16 × 6 + 4, so 3100 ≡ 3⁴ = 81. Finally 81 = 11 × 7 + 4, so the residue is 4. M1 for using Fermat, M1 for reducing the exponent, A1 for the residue 4.Find the last digit of 72024.
Worked answer
The last digit is the residue modulo 10. Powers of 7 give 7, 9, 3, 1 and then repeat, so 7⁴ ≡ 1 (mod 10). Since 2024 is a multiple of 4, 72024 ≡ 1 and the last digit is 1. M1 for working modulo 10, A1 for the cycle of length 4, A1 for the last digit. Fermat does not apply directly here, because 10 is not prime, but the cycle is still there.Solve the congruence 5x ≡ 4 (mod 13).
Worked answer
Since 5 and 13 are coprime, 5 has an inverse. Trying multiples: 5 × 8 = 40 = 3 × 13 + 1, so the inverse is 8. Multiplying both sides gives x ≡ 32 (mod 13), and 32 = 2 × 13 + 6, so x ≡ 6 (mod 13). M1 for seeking the inverse of 5, A1 for the inverse 8, M1 for multiplying through, A1 for the residue 6. Checking: 5 × 6 = 30 = 2 × 13 + 4.Use congruences to test 8294 and 8291 for divisibility by 11, and justify the test you use.
Worked answer
Since 10 ≡ −1 (mod 11), powers of 10 alternate between 1 and −1, so a number is congruent to its alternating digit sum taken from the right. For 8294 that is 4 − 9 + 2 − 8 = −11, a multiple of 11, so 8294 is divisible (it is 11 × 754). For 8291 it is 1 − 9 + 2 − 8 = −14, which is not, so 8291 is not. B1 for 10 ≡ −1 (mod 11), M1 for the alternating digit sum, A1 for 8294, A1 for 8291.Show that the cube of any integer is congruent to 0, 1 or −1 modulo 9.
Worked answer
Every integer is congruent to one of 0, ±1, ±2, ±3, ±4 modulo 9, and cubing those gives 0, ±1, ±8, ±27, ±64. Reducing: ±8 ≡ ∓1, ±27 ≡ 0 and ±64 ≡ ±1. So the only residues that occur are 0, 1 and 8, that is 0 and ±1. M1 for considering every residue mod 9, A1 for the reduced cubes, A1 for the conclusion. Any integer claimed to be a cube must pass that test.Find the remainder when 1581 is divided by 13.
Worked answer
First reduce the base: 15 ≡ 2 (mod 13), so the problem becomes 281. Since 13 is prime and 2 is not a multiple of it, Fermat gives 2¹² ≡ 1, so the exponent may be reduced modulo 12.
81 = 6 × 12 + 9, leaving 2⁹ = 512. Finally 512 = 39 × 13 + 5, so the remainder is 5. M1 for reducing the base, M1 for reducing the exponent by Fermat, A1 for 2⁹ = 512, A1 for the remainder 5. Reducing the base and the exponent separately kept every number below 512; reducing the exponent modulo 13 rather than 12 is the standard error.Prove that n⁷ − n is divisible by 42 for every integer n.
Worked answer
42 = 2 × 3 × 7, three distinct primes. Show that each divides n⁷ − n, and since they are pairwise coprime their product must divide it too. That last sentence is a mark on its own; without it the three parts prove nothing together.
Mod 7. Fermat's little theorem gives n⁷ ≡ n (mod 7) directly, so 7 divides n⁷ − n. Use the np ≡ n form, not np−1 ≡ 1, which needs n not to be a multiple of 7. The first form holds for every n, including the multiples.
Mod 3. Fermat gives n³ ≡ n (mod 3). Then n⁷ = (n³)²n ≡ n²·n = n³ ≡ n, so 3 divides n⁷ − n.
Mod 2. Fermat gives n² ≡ n (mod 2). Then n⁷ = (n²)³n ≡ n³·n = n⁴ ≡ n, so 2 divides n⁷ − n. Checking n even and n odd separately does the same job in one line.
Each of 2, 3 and 7 divides n⁷ − n, and they share no factor, so 42 divides n⁷ − n for every integer n.
B1 for 42 = 2 × 3 × 7 with the coprime argument, B1 for the mod 7 case, M1 for reducing n⁷ modulo 3, A1 for 3 dividing n⁷ − n, M1 for reducing n⁷ modulo 2, A1 for 2 dividing n⁷ − n.
The choice of 7 is not an accident. The same argument shows p divides np − n for any prime p, and 42 is the product of every prime q for which q − 1 divides 6.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise modular arithmetic and fermat's little theorem one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.