Math
Modular arithmetic calculator
Choose an operation and enter whole numbers (as large as you like). The calculator reduces mod n, raises to powers, finds inverses and solves linear congruences, showing the working for each.
| Bit i | Bit of 13 | 4^(2^i) mod 497 | Running product |
|---|---|---|---|
| 0 | 1 | 4 | 4 |
| 1 | 0 | 16 | 4 |
| 2 | 1 | 256 | 30 |
| 3 | 1 | 429 | 445 |
Show the working, step by step
Write the exponent in binary.
13 = 1101₂ = 2⁰ + 2² + 2³
Square repeatedly, reducing mod 497 each time: 4, 4², 4⁴, 4⁸, …
4^1 ≡ 4 4^2 ≡ 16 4^4 ≡ 256 4^8 ≡ 429
Multiply together the powers whose bit is 1, reducing as you go.
4 × 256 × 429 ≡ 445 (mod 497)
Square-and-multiply needs about log₂ e steps (4 here) instead of e − 1 multiplications, and reducing after every step keeps the numbers below n². This is how RSA and Diffie–Hellman are computed.
The rules that make it work
(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ᵉ mod n: square and multiply, reducing after every step
Because sums and products can be reduced at any stage, the numbers never need to grow beyond n². That is what lets computers work with powers such as 7^(10¹⁰⁰) mod n, whose full value would have more digits than there are atoms in the universe.
A worked example: 4¹³ mod 497
- 13 in binary is 1101, so 4¹³ = 4⁸ × 4⁴ × 4¹.
- Square repeatedly mod 497: 4¹ ≡ 4, 4² ≡ 16, 4⁴ ≡ 256, 4⁸ ≡ 256² = 65,536 ≡ 429.
- Multiply the powers whose bit is 1: 4 × 256 = 1,024 ≡ 30; then 30 × 429 = 12,870 ≡ 445.
Three squarings and two multiplications replace twelve multiplications. For an exponent with 300 digits, the saving is the difference between about 1,000 steps and more steps than could ever be carried out.
The negative-number convention
| Expression | Mathematics / Python | C, Java, JavaScript |
|---|---|---|
| 17 mod 5 | 2 | 2 |
| −17 mod 5 | 3 | −2 |
| −5 mod 5 | 0 | 0 (−0 in JavaScript) |
This calculator always returns the least non-negative residue, 0 to n − 1, which is what number theory, cryptography and the other modes here assume.
Where modular arithmetic is used
- Check digits. ISBN-10 uses a weighted sum mod 11; bank IBANs are checked mod 97.
- Cryptography. RSA encrypts with c = mᵉ mod n and Diffie–Hellman exchanges gᵃ mod p, both computed by square-and-multiply.
- Calendars and clocks. 100 days after a Monday is a Wednesday, because 100 mod 7 = 2.
- Hashing and random numbers. Many hash tables and pseudo-random generators reduce a large value mod the table size or a large prime.
Common mistakes
- Dividing in modular arithmetic. There is no plain division; multiply by an inverse instead, and only when one exists.
- Cancelling a common factor without changing the modulus. 6x ≡ 9 (mod 15) becomes 2x ≡ 3 (mod 5), not 2x ≡ 3 (mod 15).
- Computing aᵉ in full before reducing. It overflows long before the answer is reached.
Common questions
What does a mod n mean?
The remainder when a is divided by n, taken between 0 and n − 1. 17 mod 5 = 2 because 17 = 3 × 5 + 2. Two numbers are congruent mod n, written a ≡ b (mod n), when they leave the same remainder, which is the same as n dividing a − b. Clock arithmetic is mod 12.
What is −17 mod 5?
In mathematics it is 3, because −17 = 5 × (−4) + 3 and remainders are kept between 0 and 4. Python’s % gives 3 too. C, Java and JavaScript truncate the quotient towards zero instead, so −17 % 5 is −2 there. The two answers differ by exactly 5, so they are congruent; choose “a mod n” to see both.
How does square-and-multiply compute a huge power?
Write the exponent in binary, square the base repeatedly (a, a², a⁴, a⁸, …) reducing mod n each time, and multiply together the squares whose binary digit is 1. For 4¹³ mod 497, 13 = 1101₂ = 8 + 4 + 1, so the answer is 4⁸ × 4⁴ × 4¹ ≡ 429 × 256 × 4 ≡ 445. It takes about log₂ e steps, so an exponent with hundreds of digits is no problem.
When does a modular inverse exist?
a has an inverse mod n exactly when GCD(a, n) = 1. Then the extended Euclidean algorithm finds x with a·x ≡ 1 (mod n). For example 3⁻¹ ≡ 4 (mod 11), since 3 × 4 = 12 ≡ 1. But 6 has no inverse mod 15, because 6 and 15 share the factor 3.
How do I solve a linear congruence a·x ≡ b (mod n)?
Let g = GCD(a, n). If g does not divide b there is no solution. Otherwise divide a, b and n by g, multiply by the inverse of a/g, and you get one solution mod n/g, which is g solutions mod n. For 6x ≡ 9 (mod 15): g = 3, so 2x ≡ 3 (mod 5), x ≡ 3 × 3 = 9 ≡ 4 (mod 5), giving x = 4, 9 or 14 mod 15.
Related calculators
-
GCD and LCM
The Euclidean algorithm and Bézout coefficients.
-
Number theory toolbox
Euler’s totient and more.
-
Division
Quotient and remainder by long division.
-
Prime numbers
Miller–Rabin uses modular powers.
-
Number system converter
Binary, used by square-and-multiply.