Congruences and modular arithmetic

On this page

What is the last digit of 3²⁰²⁶? Can x²-3y² = 2 have a solution in integers? Both questions are about remainders, and modular arithmetic is the algebra of remainders. It lets you replace huge numbers by small ones, and it reduces a statement about all integers to a handful of cases. This lesson defines congruence, shows which operations it respects and which it does not, and uses it to find remainders of large powers and to prove that certain equations have no integer solutions.

Congruence keeps only the remainder

For a positive integer n, integers a and b are congruent modulo n when n divides their difference:

a≡ bpmod n ⇌ n ∣ (a-b).

Equivalently, a and b leave the same remainder on division by n. For example, 17≡2pmod5 and -1≡4pmod5.

If a≡ b and c≡ dpmod n, then for every positive integer k,

a + c≡ b + d, a-c≡ b-d,; ac≡ bd, a^k≡ b^kpmod n.

For the product, ac-bd = a(c-d) + d(a-b) is a sum of multiples of n; the power rule follows by repeated multiplication. So in any sum, difference, product or power you may replace a number by anything congruent to it.

A useful example: 10≡1pmod9, so 10^k≡1 for every k, and every integer is congruent modulo 9 to the sum of its digits. That is why a number is divisible by 9 exactly when its digit sum is.

Find the remainder when 2⁵⁰ is divided by 7.

Show full solutionHide solution

Look for a power congruent to 1
Method
2¹≡2, 2²≡4, 2³ = 8≡1pmod7.
Reason
Once a power is congruent to 1, the powers repeat in a cycle, here of length 3.
Working
Answer
Write the exponent using that cycle: 50 = 3 × 16 + 2.
Reduce the power
Working
Answer
2⁵⁰ = (2³)¹⁶ · 2²; ≡1¹⁶ · 4 = 4pmod7.
The remainder is 4.

Quick check

The remainder must be one of 0,1,…,6; a final answer outside that list is not yet reduced. Here 2⁵⁰ has 16 digits, but no step needed a number larger than 8.

Find the remainder when 7¹⁰⁰ is divided by 5.
Find the last digit of 3²⁰²⁶.

Your working for both remainders

Show answerHide answer

7≡2pmod5 and 2⁴ = 16≡1, so 7¹⁰⁰≡2¹⁰⁰ = (2⁴)²⁵≡1. The remainder is 1.
The last digit is the remainder modulo 10. 3⁴ = 81≡1pmod10 and 2026 = 4 × 506 + 2, so 3²⁰²⁶≡3² = 9. The last digit is 9.

Division needs care

You cannot always cancel: 2 × 3≡2 × 8pmod10, but 3not ≡8pmod10. Cancelling a factor c is valid when c and n have no common factor greater than 1, because then some integer c' satisfies cc'≡1pmod n, and multiplying by c' undoes the multiplication by c. For example, 5 × 3 = 15≡1pmod7, so multiplying both sides of 3x≡4pmod7 by 5 gives x≡20≡6pmod7.

A student solves 6x≡6pmod9 by cancelling the 6, and concludes that the only solution with 0 ≤ x ≤ 8 is x = 1. Find the error and all the solutions in that range.

Write your answer, then compare it with the solution

The error and every solution

Show full solutionHide solution

Return to the definition
Method
6x≡6pmod9 means 9 ∣ 6(x-1).
Reason
6 and 9 share the factor 3, so 6 has no inverse modulo 9 and cannot be cancelled.
Working
Answer
9 ∣ 6(x-1) exactly when 3 ∣ 2(x-1), that is when x≡1pmod3. So x = 1, 4 or 7; for instance 6 × 4 = 24≡6pmod9.

Common mistake

Cancelling a factor shared with the modulus loses solutions. Divide the whole congruence by the common factor, including the modulus: 6x≡6pmod9 becomes 2x≡2pmod3, and 2 can be cancelled modulo 3.

Residue classes make cases finite

Every integer is congruent modulo n to exactly one of 0,1,…,n-1. So a claim about all integers can be proved by checking these n cases, and a claim that an equation has no integer solutions can be proved by finding a modulus where no case works. Squares are the most useful case, because they take only a few values:

Modulus	Possible values of x²
3	0, 1
4	0, 1
8	0, 1, 4

For example, a sum of two squares is congruent to 0, 1 or 2 modulo 4, so no integer of the form 4k + 3 is a sum of two squares.

(a) Prove that n³ + 2n is divisible by 3 for every integer n. [3]

(b) Prove that the equation x²-3y² = 2 has no integer solutions. [2]

Write your answer, then compare it with the solution

Your proofs of (a) and (b)

Show full solutionHide solution

Check every residue modulo 3
Method
Every integer n is congruent to 0, 1 or 2 modulo 3.
Reason
These three cases cover every integer.
Working
Answer
n≡0: 0 + 0 = 0. n≡1: 1 + 2 = 3≡0. n≡2: 8 + 4 = 12≡0. In every case n³ + 2n≡0pmod3. blacksquare
Reduce the equation modulo 3
Method
If x²-3y² = 2, then x²≡2pmod3.
Reason
3y²≡0, so the equation forces a particular square residue.
Working
Answer
But squares modulo 3 are 0²≡0, 1²≡1 and 2²≡1: never 2. So there are no integer solutions. blacksquare

Self-mark with the mark scheme

Tick each mark point that your answer includes.

Tick a point only if your written proof contains it. This self-check does not record a mark.

Mark points

1 mark: Splits into the residues 0, 1 and 2 modulo 3 and says they cover all integers.
1 mark: Computes n³ + 2n modulo 3 correctly in all three cases.
1 mark: Concludes that 3 divides n³ + 2n for every integer n.
1 mark: Reduces the equation to x² ≡ 2 (mod 3).
1 mark: Shows squares are only 0 or 1 modulo 3, so no solution exists.

Common mistake

Checking n = 1,2,3,4 numerically is not a proof for all integers, including negative ones; the residue classes are. An alternative for (a): n³ + 2n = n(n²-1) + 3n = (n-1)n(n + 1) + 3n, and one of three consecutive integers is a multiple of 3.

Common mistakes

Checking a few values of n and calling it a proof. Cover every residue class, including those of negative integers.
Cancelling a factor that shares a common factor with the modulus.
Giving a “remainder” that is negative or not less than the modulus.
Reducing an exponent modulo n: 2⁵⁰not ≡2^50bmod7pmod7 in general. Reduce the base, and use a cycle for the exponent.
Choosing an unhelpful modulus. For equations with a term like 3y², try modulus 3; for sums of squares, try 4 or 8.

Before you move on

Find the remainder when 5²⁰²⁶ is divided by 13.
How many integers x with 0 ≤ x ≤ 20 satisfy 4x≡8pmod12?

1. Remainder

2. Number of solutions

Show answerHide answer

5² = 25≡-1pmod13, so 5⁴≡1. Since 2026 = 4 × 506 + 2, 5²⁰²⁶≡5²≡-1≡12. The remainder is 12.
12 ∣ 4(x-2) exactly when 3 ∣ x-2, so x≡2pmod3: x = 2,5,8,11,14,17,20. There are 7 solutions.

Syllabus and review details

GCE A-Level H3 Mathematics 2027 · 2027

Last reviewed: 2026-11-06

Read offline with Premium

Guided steps

Reading settings

Congruence keeps only the remainder

The remainder of a huge power

Look for a power congruent to 1

Reduce the power

Remainders of large powers

Division needs care

One solution, or three?

Return to the definition

Residue classes make cases finite

Cubes and squares modulo 3

Check every residue modulo 3

Reduce the equation modulo 3

Common mistakes

Before you move on

A remainder and a count of solutions

Lesson done

Congruence keeps only the remainder

The remainder of a huge power

Remainders of large powers

Division needs care

One solution, or three?

Residue classes make cases finite

Cubes and squares modulo 3

Common mistakes

Before you move on

A remainder and a count of solutions

Questions