Modular Arithmetic Calculator
Choose an operation, enter a, b and the modulus m, and get the result with the working shown: modular inverse, division, powers and linear congruences included.
What is modular arithmetic?
Modular arithmetic is arithmetic on remainders. We write a ≡ b (mod m) when m divides a − b, which means a and b leave the same remainder when divided by m. The clock is the standard picture: 15:00 is 3 o'clock because 15 ≡ 3 (mod 12). Addition, subtraction and multiplication all respect congruences, so you may reduce numbers modulo m at any moment of a calculation without changing the final remainder.
This idea is the language of number theory and cryptography. Checksums, hash functions, pseudo-random generators, RSA and Diffie–Hellman are all built from computations modulo some number m.
Operations in this calculator
Each operation reduces a and b first and then shows the remaining work.
- Add, subtract, multiply: compute with the reduced values and reduce the result into the range 0 to m − 1. A negative result such as −3 becomes m − 3.
- Power: ab mod m by square-and-multiply. A negative exponent first needs the inverse of a.
- Inverse: a−1 is the number x with a·x ≡ 1 (mod m). It exists exactly when gcd(a, m) = 1 and is found with the extended Euclidean algorithm.
- Division: a ÷ b means a · b−1, so b must be invertible modulo m.
- Linear congruence: solve a·x ≡ b (mod m). With g = gcd(a, m) it is solvable only if g divides b, and then it has exactly g solutions modulo m.
Why division needs care
In ordinary arithmetic you can divide by any non-zero number. Modulo m you can only divide by numbers that are coprime to m. Modulo 6 the number 4 has no inverse, since 4x is always even and can never be 1 more than a multiple of 6. When m is prime, every non-zero residue has an inverse, which is why arithmetic modulo a prime behaves like ordinary fractions and is used for finite fields in cryptography.
Example: solving 6x ≡ 4 (mod 10)
Here gcd(6, 10) = 2 and 2 divides 4, so there are two solutions modulo 10. Divide through by 2 to get 3x ≡ 2 (mod 5). The inverse of 3 modulo 5 is 2, so x ≡ 2 · 2 = 4 (mod 5). The solutions modulo 10 are therefore x = 4 and x = 9. Checking: 6 · 4 = 24 ≡ 4 and 6 · 9 = 54 ≡ 4 (mod 10).
Worked examples
These examples are computed by the same engine as the calculator above, so you can compare each step with your own working.
6x ≡ 4 (mod 10)
- Operation:
Solve a·x ≡ b (mod m) - a:
6 - b:
4 - Modulus m:
10
Solutions of 6x ≡ 4 (mod 10)
x ≡ 4 (mod 5)
2 solutions modulo 10
Step-by-step solution
Formula used
a·x ≡ b (mod m): let g = gcd(a, m). Solvable ⇔ g | b.
Then x ≡ (b/g)·(a/g)⁻¹ (mod m/g), giving g solutions modulo m.
NoteReduce the inputs modulo 10
a = 6 ≡ 6 (mod 10)
b = 4 ≡ 4 (mod 10)
CalculateCheck solvability
a·x ≡ b (mod m) is solvable ⇔ gcd(a, m) divides b
gcd(6, 10) = 2
2 divides 4
CalculateDivide through by the gcd
a′ = 3, b′ = 2, m′ = 5
3·x ≡ 2 (mod 5)
CalculateInverse of a′ modulo m′
a′⁻¹ ≡ 2 (mod 5)
| i | q | r | s | t |
|---|
| 0 | — | 3 | 1 | 0 |
| 1 | — | 5 | 0 | 1 |
| 2 | 0 | 3 | 1 | 0 |
| 3 | 1 | 2 | -1 | 1 |
| 4 | 1 | 1 | 2 | -1 |
| 5 | 2 | 0 | -5 | 3 |
CalculateMultiply both sides by the inverse
x ≡ b′·a′⁻¹ (mod m′)
x ≡ 2 × 2 = 4 ≡ 4 (mod 5)
ResultAll solutions modulo 10
x ≡ 4 (mod 5)
2 solutions in 0 … 9: 4, 9
CheckVerify
6 × 4 = 24 ≡ 4 (mod 10) ✓
6 × 9 = 54 ≡ 4 (mod 10) ✓
Inverse of 17 mod 3120
- Operation:
Inverse of a (mod m) - a:
17 - b:
0 - Modulus m:
3120
Step-by-step solution
Formula used
a⁻¹ exists ⇔ gcd(a, m) = 1
a·x + m·y = 1 ⇒ x ≡ a⁻¹ (mod m)
NoteReduce the inputs modulo 3120
a = 17 ≡ 17 (mod 3120)
b = 0 ≡ 0 (mod 3120)
CalculateExtended Euclidean algorithm on (a, m)
a·x + m·y = gcd(a, m) = 1 ⇒ a⁻¹ ≡ x (mod m)
17·(-367) + 3120·(2) = 1
inverse = -367 mod 3120 = 2753
| i | q | r | s | t |
|---|
| 0 | — | 17 | 1 | 0 |
| 1 | — | 3120 | 0 | 1 |
| 2 | 0 | 17 | 1 | 0 |
| 3 | 183 | 9 | -183 | 1 |
| 4 | 1 | 8 | 184 | -1 |
| 5 | 1 | 1 | -367 | 2 |
| 6 | 8 | 0 | 3120 | -17 |
CheckVerify
17 × 2753 = 46801 = 15×3120 + 1 ≡ 1 (mod 3120)
7^560 mod 561
- Operation:
a ^ b (mod m) - a:
7 - b:
560 - Modulus m:
561
Step-by-step solution
Formula used
a^b mod m by square-and-multiply: about log₂(b) multiplications
Negative exponent: a^(−k) = (a⁻¹)^k when gcd(a, m) = 1
NoteReduce the inputs modulo 561
a = 7 ≡ 7 (mod 561)
b = 560 ≡ 560 (mod 561)
CalculateSquare-and-multiply
r ← r² mod m; if the bit is 1: r ← r·a mod m
Exponent 560 in binary: 1000110000
| Position | Bit | Square | Multiply | r |
|---|
| 9 | 1 | 1 | 7 | 7 |
| 8 | 0 | 49 | — | 49 |
| 7 | 0 | 157 | — | 157 |
| 6 | 0 | 526 | — | 526 |
| 5 | 1 | 103 | 160 | 160 |
| 4 | 1 | 355 | 241 | 241 |
| 3 | 0 | 298 | — | 298 |
| 2 | 0 | 166 | — | 166 |
| 1 | 0 | 67 | — | 67 |
| 0 | 0 | 1 | — | 1 |
−7 + 20 mod 12
- Operation:
a + b (mod m) - a:
-7 - b:
20 - Modulus m:
12
Step-by-step solution
Formula used
(a ± b) mod m = ((a mod m) ± (b mod m)) mod m
(a·b) mod m = ((a mod m)·(b mod m)) mod m
NoteReduce the inputs modulo 12
a = -7 ≡ 5 (mod 12)
b = 20 ≡ 8 (mod 12)
CalculateCompute and reduce
(a + b) mod m
5 + 8 = 13
13 mod 12 = 1
CheckVerify
12 divides 13 − 1 = 12: yes ✓
5 ÷ 3 mod 7
- Operation:
a ÷ b (mod m) - a:
5 - b:
3 - Modulus m:
7
Step-by-step solution
Formula used
a / b ≡ a·b⁻¹ (mod m), defined when gcd(b, m) = 1
NoteReduce the inputs modulo 7
a = 5 ≡ 5 (mod 7)
b = 3 ≡ 3 (mod 7)
CalculateFind b⁻¹ (mod 7)
a·x + m·y = gcd(a, m) = 1 ⇒ a⁻¹ ≡ x (mod m)
3·(-2) + 7·(1) = 1
inverse = -2 mod 7 = 5
| i | q | r | s | t |
|---|
| 0 | — | 3 | 1 | 0 |
| 1 | — | 7 | 0 | 1 |
| 2 | 0 | 3 | 1 | 0 |
| 3 | 2 | 1 | -2 | 1 |
| 4 | 3 | 0 | 7 | -3 |
CalculateMultiply a by b⁻¹
a / b ≡ a · b⁻¹ (mod m)
5 × 5 = 25
25 mod 7 = 4
CheckVerify
b × result = 3 × 4 = 12 ≡ 5 ≡ a (mod 7) ✓
Frequently asked questions
How do I compute a negative number mod m?
Add multiples of m until the result lies between 0 and m − 1. For example −7 mod 5 = 3, because −7 + 10 = 3. The calculator does this automatically.
When does a modular inverse exist?
The inverse of a modulo m exists exactly when gcd(a, m) = 1. If m is prime, every a that is not a multiple of m has an inverse.
How many solutions does ax ≡ b (mod m) have?
None if gcd(a, m) does not divide b; otherwise exactly gcd(a, m) solutions modulo m.
Is the result of mod always positive?
In mathematics the residue is chosen between 0 and m − 1. Some programming languages return a negative result for a negative dividend, so check the convention when you compare with code.