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.
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.
- Finding the last digit of a large power.
- Solving congruences such as 3x ≡ 4 (mod 7).
- Checking divisibility and building codes.
How to solve it
- a mod n: divide and keep the remainder. Negative numbers still give a result from 0 to n - 1.
- For big powers, square repeatedly and reduce mod n at every step.
- The inverse of a mod n exists only when gcd(a, n) = 1. Find it with the extended Euclidean algorithm.
- Solve ax ≡ b (mod n): there are solutions only if gcd(a, n) divides b.
- 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)Use repeated squaring, reducing mod 7 at every step
Never work out the huge power first: reduce after each multiplication.
3100mod7
Binary of the power
Multiply in the squares that match each 1 bit.
100=11001002
Result
3100≡4(mod7)
Check: multiply 100 times, reducing each time
gives 4 ✓
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)Use repeated squaring, reducing mod 13 at every step
Never work out the huge power first: reduce after each multiplication.
7200mod13
Binary of the power
Multiply in the squares that match each 1 bit.
200=110010002
Result
7200≡3(mod13)
Check: multiply 200 times, reducing each time
gives 3 ✓
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
−7mod3=2Divide and find the remainder
The remainder is always between 0 and 2, even for negative numbers.
−7=−3×3+2
Check: rebuild the number
−3×3+2=−7=−7 ✓
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)Extended Euclid: find x with 7x + 26y = 1
Reducing x mod 26 gives 15.
7×−11+26×3=1
Check: multiply and reduce
7×15=105≡1(mod26) ✓
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)The congruence
3x≡4(mod7)
gcd test
The gcd is 1, so there is exactly one solution mod 7.
gcd(3,7)=1
Check: substitute each solution
3×6=18≡4 ✓
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)The congruence
6x≡4(mod10)
gcd test
The gcd divides 4, so there are 2 solutions mod 10.
gcd(6,10)=2
Check: substitute each solution
6×4=24≡4, 6×9=54≡4 ✓
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.
- Add a multiple of 3−7 + 9
- Check: 2 ✓2
A power
Find 3¹⁰⁰ mod 7.
- 3⁶ ≡ 1100 = 6 × 16 + 4
- 3⁴81 mod 7
- Check: 4 ✓4
An inverse Higher
Inverse of 7 mod 26.
- Find x with 7x ≡ 17 × 15 = 105 = 4 × 26 + 1
- Check: 15 ✓1
A congruence Higher
Solve 3x ≡ 4 mod 7.
- Inverse of 3 is 5x ≡ 20 ≡ 6
- 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
Remainder is non-negative.
Find the cycle of a power.
Inverse needs gcd = 1.
Reduce early.
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.