Modular arithmetic
Modulo calculator
Arithmetic in ℤ/mℤ, including fast modular exponentiation and the modular inverse.
Results are the least non-negative residue. Exponents must be zero or greater.
Try
- (17 ^ 5) mod 7
- 5
Calculator
Modular arithmetic calculator
Add, multiply, exponentiate and invert modulo n, with a positive remainder and an honest answer when no inverse exists.
- No account needed
- Nothing leaves your browser
- Works offline
What is in here
7topics
534problems
54formulas
60proof tasks
Calculators
Discrete math tools
Six calculators that run entirely in this browser. Inputs are validated, so a rejected entry says what is wrong instead of returning a confident wrong answer.
About the modular arithmetic calculator
Modular arithmetic works with remainders. Writing a is congruent to b modulo n means a and b leave the same remainder on division by n, which is the same as saying n divides their difference. Clock arithmetic is the familiar case: 10 o'clock plus 5 hours is 3 o'clock, because 15 is congruent to 3 modulo 12.
The calculator always reports the least non-negative remainder, so a negative input such as -7 modulo 5 comes back as 3 rather than -2. That is the convention most textbooks use and the one that makes residue classes line up with 0 through n minus 1.
Modular exponentiation is computed by repeated squaring rather than by forming the power first, so a large exponent stays fast and exact. A modular inverse of a modulo n exists only when a and n are coprime, and when it does not exist the calculator says so instead of returning a number that fails to check.
Worked example
Worked example
Input
3 to the power 100, modulo 7Result
3^100 mod 7 = 4The powers of 3 modulo 7 repeat every 6 steps, and 100 leaves remainder 4 on division by 6.
Questions
Frequently asked
What does a mod n mean?
It is the remainder left when a is divided by n. This calculator reports the least non-negative remainder, so the answer is always between 0 and n minus 1, including for negative inputs.
When does a modular inverse exist?
The inverse of a modulo n exists exactly when the greatest common divisor of a and n is 1. If they share a factor there is no integer x with a times x congruent to 1 modulo n, and the calculator reports that rather than guessing.
How is a large modular power computed?
By repeated squaring: the exponent is read in binary and the running value is squared and reduced modulo n at each step. That keeps every intermediate value smaller than n squared instead of forming an astronomically large power.