Mod, powers mod n, inverses and congruences

Modular arithmetic works with remainders, like a clock. a mod n is the remainder when a is divided by n, always between 0 and n - 1.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What this topic covers

Reduce numbers mod m, and reduce powers step by step. Divisibility tests such as digit sums and the rule for 11 use it, and number theory results include Euler’s criterion, quadratic reciprocity and squares modulo 4 and 8. See also HCF and LCM.

Each part of this topic has its own page with the formula, worked examples and a solver: Digit sum and divisibility by 9 and 3, Divisibility rule for 11, Legendre’s formula (powers of p in n!), Pythagorean triples, Squares modulo 4 and 8, Sum of two squares theorem, Fibonacci: Cassini’s identity, Fibonacci: sum, Fibonacci: gcd, Pell equation recurrence.

Closely related topics: HCF and LCM, Surds and indices, Logic and truth tables, Sequences and nth term.

What is it used for?

Modular arithmetic works with remainders. It is used for repeating cycles, divisibility tests, codes and cryptography.

How to solve it

  1. a mod n: divide and keep the remainder. Negative numbers still give a result from 0 to n - 1.
  2. For big powers, square repeatedly and reduce mod n at every step.
  3. The inverse of a mod n exists only when gcd(a, n) = 1. Find it with the extended Euclidean algorithm.
  4. Solve ax ≡ b (mod n): there are solutions only if gcd(a, n) divides b.
  5. Check by substituting back.

Worked examples

The examples marked with a button were worked out by the solver on this page. You can try each one yourself.

Example 1: 3^100 mod 7

Worked out by the solver on this page. Press the button to try it yourself.

Modular arithmetic Answer checked
Answer
3100≡4(mod7)3^{100} \equiv 4 \pmod{7}
  1. Use repeated squaring, reducing mod 7 at every step
    Never work out the huge power first: reduce after each multiplication.
  2. Binary of the power
    Multiply in the squares that match each 1 bit.
  3. Result
  4. Check: multiply 100 times, reducing each time

Example 2: 7^200 mod 13

Worked out by the solver on this page. Press the button to try it yourself.

Modular arithmetic Answer checked
Answer
7200≡3(mod13)7^{200} \equiv 3 \pmod{13}
  1. Use repeated squaring, reducing mod 13 at every step
    Never work out the huge power first: reduce after each multiplication.
  2. Binary of the power
    Multiply in the squares that match each 1 bit.
  3. Result
  4. Check: multiply 200 times, reducing each time

Example 3: -7 mod 3

Worked out by the solver on this page. Press the button to try it yourself.

Modular arithmetic Answer checked
Answer
−7 mod 3=2-7 \bmod 3 = 2
  1. Divide and find the remainder
    The remainder is always between 0 and 2, even for negative numbers.
  2. Check: rebuild the number

Example 4: inverse of 7 mod 26

Worked out by the solver on this page. Press the button to try it yourself.

Modular arithmetic Answer checked
Answer
7−1≡15(mod26)7^{-1} \equiv 15 \pmod{26}
  1. Extended Euclid: find x with 7x + 26y = 1
    Reducing x mod 26 gives 15.
  2. Check: multiply and reduce

Example 5: solve 3x ≡ 4 mod 7

Worked out by the solver on this page. Press the button to try it yourself.

Modular arithmetic Answer checked
Answer
x≡6(mod7)x \equiv 6 \pmod{7}
  1. The congruence
  2. gcd test
    The gcd is 1, so there is exactly one solution mod 7.
  3. Check: substitute each solution

Example 6: solve 6x = 4 mod 10

Worked out by the solver on this page. Press the button to try it yourself.

Modular arithmetic Answer checked
Answer
x≡4(mod5)  (2 solutions mod 10:4,9)x \equiv 4 \pmod{5}\ \ (2\text{ solutions mod } 10: 4, 9)
  1. The congruence
  2. gcd test
    The gcd divides 4, so there are 2 solutions mod 10.
  3. Check: substitute each solution

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

A negative number

−7 mod 3 = 2

Add 9: 2.

A power

3¹⁰⁰ mod 7 = 4

3⁶ ≡ 1, so 3¹⁰⁰ ≡ 3⁴.

An inverse

inverse of 7 mod 26 is 15

7 × 15 = 105 ≡ 1.

A congruence

3x ≡ 4 (mod 7): x = 6

3 × 6 = 18 ≡ 4.

Word problems

Reduce to the remainder, use cycles for powers, and use the inverse to solve congruences.

A negative number

Find −7 mod 3.

  1. Add a multiple of 3−7 + 9
  2. Check: 2 ✓2

A power

Find 3¹⁰⁰ mod 7.

  1. 3⁶ ≡ 1100 = 6 × 16 + 4
  2. 3⁴81 mod 7
  3. Check: 4 ✓4

An inverse Higher

Inverse of 7 mod 26.

  1. Find x with 7x ≡ 17 × 15 = 105 = 4 × 26 + 1
  2. Check: 15 ✓1

A congruence Higher

Solve 3x ≡ 4 mod 7.

  1. Inverse of 3 is 5x ≡ 20 ≡ 6
  2. Check: 18 ≡ 4 ✓6

Common mistakes

Negative remainders

−7 mod 3 = −1 ✗

2 ✓

The remainder is non-negative.

Not reducing powers

computing 3¹⁰⁰ ✗

use the cycle ✓

Reduce step by step.

Dividing in a congruence

3x ≡ 4 so x ≡ 4/3 ✗

multiply by the inverse ✓

Division is not allowed.

Inverse not existing

every number has an inverse ✗

only if coprime to m ✓

gcd must be 1.

Exam tips

  1. Remainder is non-negative.
  2. Find the cycle of a power.
  3. Inverse needs gcd = 1.
  4. Reduce early.
  5. Check by substitution.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. 17 mod 5 Foundation

2

2. −3 mod 7 Foundation

4

3. 2¹⁰ mod 7 (2³ ≡ 1) Foundation

2

4. Inverse of 3 mod 7 Higher

5

5. 5 × 6 mod 7 Higher

2

6. Solve 2x ≡ 3 mod 5: x Higher

4

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Modulus
The number m.
Congruent
Same remainder mod m.
Residue
The remainder.
Modular inverse
a⁻¹ with aa⁻¹ ≡ 1.
Coprime
gcd = 1.
Order
Smallest power giving 1.

Frequently asked questions

What does a ≡ b (mod m) mean?

a and b leave the same remainder on division by m.

How do I find a large power mod m?

Find the cycle and reduce the exponent.

When does an inverse exist?

When the number is coprime to the modulus.

Which page covers divisibility by 9?

digit sums.

Which page covers divisibility by 11?

rule for 11.

Which page covers squares mod n?

squares modulo 4 and 8.

More in Discrete maths and number theory and the formula sheets.