How to use it
- Choose the Operation: a mod n, the inverse, a power, or the Chinese remainder theorem.
- Type the Number a, the Exponent e and the Modulus n where they are asked for, or one congruence per line in Congruences (one per line).
- Read Result. For the inverse, the Check box says whether it exists.
- Go through How it is worked out; the tables show the Euclid rows or the binary digits.
Residues, inverses and powers
The residue of a modulo n is the number r with 0 ≤ r < n and a = q·n + r, so a mod n is never negative: −17 mod 5 is 3, because −17 = (−4)·5 + 3. An inverse of a modulo n is a number x with a·x ≡ 1 (mod n). It exists exactly when gcd(a, n) = 1, and the extended Euclidean algorithm finds it. A power a^e mod n is computed by square-and-multiply, which uses one squaring per binary digit of e.
a mod n = a − n·⌊a ÷ n⌋
If s·a + t·n = 1, then a⁻¹ ≡ s (mod n)- Many calculators return −2 for −17 mod 5, the remainder of truncated division. That is not the residue, which is always from 0 to n − 1.
- A power with a negative exponent uses the inverse of a, so it exists only when gcd(a, n) = 1.
- The Euclid table and the binary table show every intermediate number, so the working can be checked by hand.
The Chinese remainder theorem and what the calculator does not cover
The Chinese remainder theorem finds one number x that leaves the remainder rᵢ when divided by mᵢ, for every congruence of a system. When the moduli are pairwise coprime there is always exactly one solution modulo their product. When they are not, the remainders must agree modulo the gcds of the moduli, or the system has no solution.
- Very large exponents with more than 64 binary digits are refused, so that the working stays readable.
- Congruences with a variable other than x, polynomial congruences and modular square roots are not covered.
- The calculator works with whole numbers only; a decimal is refused.
Worked example: 4¹³ mod 497, and the other operations
The exponent 13 is 1101 in binary. Starting from 1 and squaring at each digit, with a multiplication by 4 at each 1, the results are 4, 64, 120 and then 445, so 4¹³ mod 497 = 445. The same method runs in the calculator with its table of digits.
The other examples: −17 mod 5 = 3; the inverse of 4 modulo 7 is 2, because 4 × 2 = 8 ≡ 1; and x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) has the solution x ≡ 23 (mod 105).
| Question | Answer |
|---|---|
| 4^13 mod 497 | 445 |
| −17 mod 5 | 3 |
| Inverse of 4 modulo 7 | 2 |
| x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7) | x ≡ 23 (mod 105) |
Frequently asked questions
Why is −17 mod 5 equal to 3 and not −2?
The residue is the remainder that is never negative, with 0 ≤ r < n. Since −17 = (−4) × 5 + 3, the residue is 3. Many calculators show −2, which is the remainder of truncated division, not the modular residue.
When does a number have an inverse modulo n?
When the greatest common divisor of the number and n is 1. For example 4 has an inverse modulo 7, which is 2, but 4 has none modulo 6, because gcd(4, 6) = 2.
Why does the power use squares and not repeated multiplication?
Squaring and reducing at each binary digit keeps every number small. For 4¹³ the largest intermediate value is 484 × 4 = 1936, instead of a number with about 8 digits that a long product would produce.
What if the congruences have moduli that share a factor?
The system can still have a solution. The remainders must agree modulo the gcd of the two moduli: x ≡ 2 (mod 4) and x ≡ 8 (mod 6) agree, and the solution is x ≡ 2 (mod 12).
Are my numbers sent to a server?
No. The calculation runs in your browser, and nothing you type is sent to us.
Sources
- Wikipedia: Modular arithmetic
- Wikipedia: Modular exponentiation
- Wikipedia: Extended Euclidean algorithm
- Wikipedia: Chinese remainder theorem
Figures and text last checked on Tuesday, November 10, 2026.