Modular Arithmetic Calculator (mod, Inverse & More)
A modular arithmetic calculator works with remainders: a mod n is what is left after dividing a by n, written from 0 to n − 1. For example, 38 mod 12 = 2, because 38 = 3 × 12 + 2. Sums, products and powers work the same way: 38 × 27 mod 12 = 6, and 3²⁰⁰ mod 13 = 9.
−17 mod 5 = 3 because −17 = −4 × 5 + 3. Programming languages can give a different sign: −2 with truncated division (C, Java, JavaScript %), 3 with floored division (Python %, Excel MOD).
| Convention | q | r |
|---|---|---|
| Math (Euclidean): remainder never negativetextbooks, number theory, this calculator | −4 | 3 |
| Truncated: quotient rounded toward 0C, C++, Java, JavaScript, C# (%) | −3 | −2 |
| Floored: quotient rounded downPython (%), Excel MOD, Ruby | −4 | 3 |
| Symmetric: smallest sizebalanced representation | − | −2 |
Show steps
- Divide: −17 ÷ 5 ≈ −3.4.
- For the math convention choose the whole-number quotient q that leaves a remainder r with 0 ≤ r < 5: q = −4.
- Multiply back and subtract: r = −17 − (−4 × 5) = −17 − (−20) = 3.
- Check: −4 × 5 + 3 = −17.
- Negative numbers: truncated division rounds −17 ÷ 5 toward zero to q = −3, giving remainder −2 (same sign as a). Floored division rounds down to q = −4, giving 3 (same sign as n). All of these differ by a multiple of n, so they are congruent: 3 ≡ −2 (mod 5).
Calculator shortcut for positive numbers: divide, drop the decimals to get q, multiply q by n and subtract from a.
How to use the modular arithmetic calculator
- Pick an operation: a mod n, + − × ÷, Power, Inverse, or Solve for a congruence ax ≡ b (mod n).
- Enter whole numbers (any size) and the modulus n. The a mod n tab also takes negative numbers and decimals.
- Read the answer, the supporting values and the clock picture, then open Show steps for the full working and the tables.
What is modular arithmetic?
Modular arithmetic is arithmetic on a clock. With modulus n you only keep the remainder after dividing by n, so the numbers wrap around after n − 1. On a 12-hour clock, 11 + 8 = 19, and 19 mod 12 = 7: eight hours after 11 o’clock it is 7 o’clock.
Two numbers are congruent modulo n, written a ≡ b (mod n), when they leave the same remainder, which is the same as saying n divides a − b. For example 38 ≡ 2 (mod 12) because 38 − 2 = 36 = 3 × 12.
How to find a mod n
- Divide a by n and keep the whole-number quotient q.
- Multiply back: q × n.
- Subtract: r = a − q × n. This r is a mod n.
For 250 mod 24: 250 ÷ 24 ≈ 10.42, so q = 10; 10 × 24 = 240; 250 − 240 = 10. So 250 mod 24 = 10.
a mod n with negative numbers
In mathematics the remainder is always between 0 and n − 1, so you choose the quotient that rounds down. For −17 mod 5: −17 ÷ 5 = −3.4, round down to q = −4, and r = −17 − (−20) = 3. So −17 mod 5 = 3.
Programming languages do not all agree. C, C++, Java and JavaScript round the quotient toward zero, so -17 % 5 gives −2. Python’s % and Excel’s MOD round down and give 3. Both answers are correct in the sense that −2 ≡ 3 (mod 5); they differ by exactly 5. The calculator shows every convention side by side.
| Expression | Math (0 to n − 1) | C, Java, JavaScript % | Python %, Excel MOD |
|---|---|---|---|
| 17 mod 5 | 2 | 2 | 2 |
| −17 mod 5 | 3 | −2 | 3 |
| 17 mod −5 | 2 | 2 | −3 |
| −7 mod 3 | 2 | −1 | 2 |
Rules for modular addition, subtraction and multiplication
You can reduce before or after you calculate, and the answer is the same:
- (a + b) mod n = ((a mod n) + (b mod n)) mod n
- (a − b) mod n = ((a mod n) − (b mod n)) mod n
- (a × b) mod n = ((a mod n) × (b mod n)) mod n
Example: 38 × 27 mod 12. Reduce first: 38 mod 12 = 2 and 27 mod 12 = 3. Then 2 × 3 = 6, so 38 × 27 ≡ 6 (mod 12). Check without reducing: 38 × 27 = 1,026 and 1,026 = 85 × 12 + 6.
Division is different. Dividing by b means multiplying by the modular inverse of b, which exists only when gcd(b, n) = 1. For example 4 ÷ 3 (mod 7) = 4 × 5 = 20 ≡ 6, because 3 × 5 = 15 ≡ 1 (mod 7).
Fast modular exponentiation (square and multiply)
To find ae mod n without huge numbers, write e in binary, square repeatedly and multiply in only the squares whose bit is 1, reducing mod n every time.
Example: 3²⁰⁰ mod 13. In binary 200 = 11001000, so 200 = 128 + 64 + 8. The squares mod 13 are 3, 9, 3, 9, 3, 9, 3, 9 for the powers 1, 2, 4, 8, 16, 32, 64, 128. Multiply the ones for 8, 64 and 128: 9 × 3 × 9 = 243, and 243 mod 13 = 9. So 3²⁰⁰ mod 13 = 9 after only 7 squarings and 3 multiplications.
How to find a modular inverse
The inverse of a mod n is the number x with a × x ≡ 1 (mod n). It exists only when gcd(a, n) = 1. The extended Euclidean algorithm finds it.
Example: the inverse of 7 mod 26. Divide repeatedly: 26 = 3 × 7 + 5, 7 = 1 × 5 + 2, 5 = 2 × 2 + 1. Working back gives 1 = 3 × 26 − 11 × 7. Read mod 26, this says −11 × 7 ≡ 1, and −11 + 26 = 15. So 7⁻¹ ≡ 15 (mod 26). Check: 7 × 15 = 105 = 4 × 26 + 1.
6 has no inverse mod 9, because gcd(6, 9) = 3: every multiple of 6 is 0, 6 or 3 mod 9, never 1.
How to solve ax ≡ b (mod n)
- Find d = gcd(a, n). If d does not divide b, there is no solution.
- Otherwise divide a, b and n by d.
- Multiply both sides by the inverse of a/d modulo n/d.
- The answer x ≡ x₀ (mod n/d) gives d solutions modulo n.
Example: 4x ≡ 8 (mod 11). gcd(4, 11) = 1 and 4⁻¹ ≡ 3 (mod 11), since 4 × 3 = 12 ≡ 1. Then x ≡ 8 × 3 = 24 ≡ 2 (mod 11). Check: 4 × 2 = 8.
Example with two solutions: 6x ≡ 4 (mod 10). gcd(6, 10) = 2 divides 4, so divide by 2: 3x ≡ 2 (mod 5). The inverse of 3 mod 5 is 2, so x ≡ 4 (mod 5), and modulo 10 the solutions are x = 4 and x = 9.
Common mistakes
| Mistake | Fix |
|---|---|
| Writing −17 mod 5 = −2 in a math class | Add the modulus: −2 + 5 = 3. Math remainders are never negative. |
| Dividing both sides of a congruence like ordinary algebra | Multiply by an inverse instead, and only when the gcd is 1. |
| Computing 3²⁰⁰ in full before reducing | Reduce after every squaring and multiplication. |
| Expecting an inverse for every number | Check gcd(a, n) = 1 first; 6 has no inverse mod 9. |
Where modular arithmetic is used
- Time and calendars: hours wrap mod 12 or 24, weekdays mod 7.
- Check digits: ISBN-10 uses mod 11 and many ID numbers use mod 10 checks.
- Cryptography: RSA uses modular powers and inverses. In the classic toy example n = 3233, e = 17 and the private key 2753 is the inverse of 17 mod 3120.
- Programming: hash tables, cycling through arrays and testing even or odd with % 2.
Modular Arithmetic practice quiz: 10 questions
Test yourself with 10 multiple-choice questions. Choose an answer and press Submit to see if you are right and why. Your score appears at the end.
47 = 7 × 6 + 5, so the remainder is 5. 7 is the quotient, not the remainder.
Round −23 ÷ 6 = −3.83… down to −4: −23 − (−24) = 1. −5 is what C, Java and JavaScript % return.
58 ≡ 2 and 41 ≡ 6 (mod 7), so the product is ≡ 2 × 6 = 12 ≡ 5 (mod 7).
2¹⁰ = 1,024 = 93 × 11 + 1. This matches Fermat's little theorem, since 11 is prime.
5 × 5 = 25 = 2 × 12 + 1, so 5 is its own inverse mod 12. gcd(5, 12) = 1, so an inverse exists.
gcd(4, 10) = 2, not 1. The others are coprime to 10: 3 × 7 = 21 ≡ 1 and 9 × 9 = 81 ≡ 1.
The inverse of 3 mod 7 is 5, so x ≡ 4 × 5 = 20 ≡ 6. Check: 3 × 6 = 18 ≡ 4.
Quiz complete
Frequently asked questions
How do you do modular arithmetic?
Calculate as usual, then replace the result by its remainder after dividing by n. You may reduce the inputs first to keep numbers small: (38 + 27) mod 12 = (2 + 3) mod 12 = 5.
How do you do modular arithmetic on a calculator?
Divide a by n, drop the decimal part to get q, multiply q by n and subtract from a. For 250 mod 24: 250 ÷ 24 = 10.41…, 10 × 24 = 240, and 250 − 240 = 10. For a negative a, round the quotient down instead, or add n to a negative remainder.
How do you solve modular arithmetic problems such as 3x ≡ 5 (mod 7)?
Multiply both sides by the inverse of 3 mod 7, which is 5 because 3 × 5 = 15 ≡ 1. Then x ≡ 25 ≡ 4 (mod 7). Check: 3 × 4 = 12 ≡ 5 (mod 7).
How do you find a modular inverse?
First check that gcd(a, n) = 1. For a small modulus, try x = 1, 2, 3, … until a × x mod n = 1; for 3 mod 11 that gives 4, since 12 ≡ 1. For large numbers use the extended Euclidean algorithm, which the Inverse tab shows as a table.
How do you calculate modular exponents?
Use repeated squaring: square the base again and again, reducing mod n each time, and multiply together the squares that match the 1 bits of the exponent. 7¹³ mod 11 = 2, using 13 = 8 + 4 + 1.
Why does my programming language give a negative mod?
Languages such as C, Java and JavaScript define % with the quotient rounded toward zero, so the remainder takes the sign of a. To get the math answer, use ((a % n) + n) % n.
Related calculators
Related to This Article
More math articles
- Overview of the SAT Mathematics Test
- How to Graph the Cosine Function?
- Reproduction and Variation
- Finding Text Evidence
- Transition to Racial Slavery: Law, Labor and Inherited Status
- Place Value Word Problems
- Free Printable Grade 2 Math Worksheets for West Virginia
- The Best Grade 3 ELA Practice Tests for Georgia Students
- Seniority
- From Tables and Graphs to Equations: How to Master Proportional Relationships
What people say about "Modular Arithmetic Calculator (mod, Inverse & More)"?
No one replied yet.