Questions on modular arithmetic and Fermat's little theorem

Question 1

Find the least positive residue of 3¹⁰⁰ modulo 7.

Accepted 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 3¹⁰⁰ ≡ 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.

Question 2

Find the last digit of 7²⁰²⁴.

Accepted 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, 7²⁰²⁴ ≡ 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.

Question 3

Explain what the statement a ≡ b (mod n) means, and find the least positive residue of −17 modulo 5.

Accepted Answer

It means that n divides a − b, so a and b leave the same remainder on division by n. B1 for the definition. Dividing, −17 = (−4) × 5 + 3, so the least positive residue is 3. B1 for 3. The remainder in the division theorem is taken from 0 to n − 1, so the quotient for a negative number goes one step further down than a calculator's truncation would suggest: −17 = (−3) × 5 − 2 is a true equation but −2 is not a residue in that range.

Question 4

Given that a ≡ 4 (mod 9) and b ≡ 7 (mod 9), find the least positive residues of a + b, of ab and of a³ modulo 9.

Accepted Answer

Congruences may be added, multiplied and raised to powers, so work with the representatives 4 and 7 throughout. a + b ≡ 4 + 7 = 11 ≡ 2. ab ≡ 4 × 7 = 28 = 3 × 9 + 1 ≡ 1. a³ ≡ 4³ = 64 = 7 × 9 + 1 ≡ 1. B1 B1 B1 for the three residues. The answers do not depend on which representatives are used: taking a = 13 and b = 16 gives 29, 208 and 2197, whose residues are the same 2, 1 and 1.

Question 5

Solve the congruence 5x ≡ 4 (mod 13).

Accepted 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.

Question 6

Use congruences to test 8294 and 8291 for divisibility by 11, and justify the test you use.

Accepted 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.

Question 7

Show that the cube of any integer is congruent to 0, 1 or −1 modulo 9.

Accepted 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.

Question 8

Find the remainder when 15⁸¹ is divided by 13.

Accepted Answer

First reduce the base: 15 ≡ 2 (mod 13), so the problem becomes 2⁸¹. 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 exponent modulo 13 rather than 12 is the standard error.

Question 9

Use congruences to prove that 3²ⁿ⁺¹ + 2ⁿ⁺² is divisible by 7 for every positive integer n.

Accepted Answer

Work modulo 7 and rewrite each term as a multiple of the same power. First, 3²ⁿ⁺¹ = 3 × (3²)ⁿ = 3 × 9ⁿ, and 9 = 7 + 2 ≡ 2 (mod 7), so raising to the power n gives 9ⁿ ≡ 2ⁿ and 3²ⁿ⁺¹ ≡ 3 × 2ⁿ (mod 7). M1 for splitting off the 3 and writing the rest as a power of 9, A1 for 3 × 2ⁿ.
Second, 2ⁿ⁺² = 2² × 2ⁿ = 4 × 2ⁿ, with no reduction needed. M1 for writing it as a multiple of 2ⁿ.
Adding, 3²ⁿ⁺¹ + 2ⁿ⁺² ≡ 3 × 2ⁿ + 4 × 2ⁿ = 7 × 2ⁿ ≡ 0 (mod 7), so 7 divides the sum for every positive integer n. A1 for collecting to 7 × 2ⁿ with the conclusion.
Checking the small cases: n = 1 gives 27 + 8 = 35 = 5 × 7, n = 2 gives 243 + 16 = 259 = 37 × 7, and n = 3 gives 2187 + 32 = 2219 = 317 × 7.

Question 10

Find all solutions of 6x ≡ 4 (mod 10), and explain why 6x ≡ 3 (mod 10) has none.

Accepted Answer

The highest common factor of 6 and 10 is 2, and 2 divides 4, so solutions exist and there are 2 of them modulo 10. B1 for the solubility test. Dividing the whole congruence, including the modulus, by 2 gives 3x ≡ 2 (mod 5). The inverse of 3 modulo 5 is 2, since 3 × 2 = 6 ≡ 1, so x ≡ 4 (mod 5). M1 for reducing to a congruence with coprime coefficient and modulus. Lifting back, x ≡ 4 or 9 (mod 10), and 6 × 4 = 24 ≡ 4 and 6 × 9 = 54 ≡ 4 both check. A1 for both solutions.
For 6x ≡ 3 (mod 10), the same factor 2 divides 6 and 10 but not 3, so the test fails and there is no solution. Concretely, 6x is always even while every number congruent to 3 modulo 10 is odd. B1 for the reason.

Question 11

Solve the simultaneous congruences x ≡ 2 (mod 5) and x ≡ 3 (mod 7), giving your answer as a single congruence.

Accepted Answer

The first congruence says x = 2 + 5t for some integer t. M1 for that substitution. Putting it into the second, 2 + 5t ≡ 3 (mod 7), so 5t ≡ 1 (mod 7). M1 for the congruence in t. The inverse of 5 modulo 7 is 3, since 5 × 3 = 15 ≡ 1, so t ≡ 3 (mod 7). A1 for t ≡ 3. Then x = 2 + 5 × 3 = 17, and since t is free to move by 7 the solution is x ≡ 17 (mod 35). A1 for the single congruence with modulus 35. Checking, 17 = 3 × 5 + 2 and 17 = 2 × 7 + 3. The modulus of the answer is the product 35 because 5 and 7 are coprime; for moduli sharing a factor the two congruences may be inconsistent instead.

Question 12

Prove that n⁷ − n is divisible by 42 for every integer n.

Accepted 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 required: 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 n^p ≡ n form, not n^p−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 same argument shows p divides n^p − n for any prime p, and 42 is the product of every prime q for which q − 1 divides 6.

Question 13

Determine which residues are squares modulo 7. Hence show that x² ≡ 3 (mod 7) has no solution, and solve x² ≡ 2 (mod 7).

Accepted Answer

Every integer is congruent to one of 0, 1, 2, 3, 4, 5, 6 modulo 7, so square each in turn: 0, 1, 4, 9 ≡ 2, 16 ≡ 2, 25 ≡ 4, 36 ≡ 1. M1 for squaring every residue. The squares modulo 7 are therefore 0, 1, 2 and 4, and 3, 5 and 6 never occur. A1 for the set.
Since 3 is not among them, x² ≡ 3 (mod 7) is insoluble: no integer squares to 3 modulo 7. A1 for the conclusion.
2 is among them, and the working above shows it arises from x ≡ 3 and from x ≡ 4, so x ≡ 3 or 4 (mod 7). M1 for reading the solutions off the table, A1 for both. The list is symmetric because x and −x have the same square, so the seven residues give at most four distinct values, and a quadratic congruence modulo an odd prime has 0 or 2 solutions unless the square root is 0.

Question 14

Show that n² ≡ 0 or 1 (mod 4) for every integer n, and hence prove that no integer congruent to 3 modulo 4 is the sum of two squares. Deduce that 2023 is not the sum of two squares.

Accepted Answer

Take n even, say n = 2k. Then n² = 4k² ≡ 0. Take n odd, say n = 2k + 1. Then n² = 4k² + 4k + 1 = 4k(k + 1) + 1 ≡ 1. M1 for splitting into the two cases, A1 for both residues.
If m = a² + b² then, modulo 4, m is a sum of two numbers each of which is 0 or 1, so m ≡ 0, 1 or 2 (mod 4). M1 for adding the possibilities, A1 for the three residues that can occur. The residue 3 is not among them, so no integer congruent to 3 modulo 4 is a sum of two squares. A1 for the conclusion.
Finally 2023 = 4 × 505 + 3, so 2023 ≡ 3 (mod 4) and 2023 is not a sum of two squares. B1 for the residue of 2023 with the deduction.

Question 15

Show that 2³⁴⁰ ≡ 1 (mod 341), and explain why this does not show that 341 is prime.

Accepted Answer

Start from a small power: 2¹⁰ = 1024 = 3 × 341 + 1, so 2¹⁰ ≡ 1 (mod 341). M1 for computing 2¹⁰, A1 for the congruence. Since 340 = 34 × 10, 2³⁴⁰ = (2¹⁰)³⁴ ≡ 1³⁴ = 1 (mod 341). M1 for splitting the exponent, A1 for the conclusion.
Fermat's little theorem says that if p is prime and p does not divide a then a^p−1 ≡ 1 (mod p). Here 341 behaves as the theorem describes a prime behaving, yet 341 = 11 × 31 and is composite, so the converse of the theorem is false and passing the test proves nothing about primality. B1 for the factorisation with that conclusion. A number that passes the test for a given base without being prime is called a pseudoprime to that base; 341 is the smallest one to base 2.