How to use the modular arithmetic calculator
- Enter the first number (a), the second number (b) and the modulus (n), which must be 2 or more.
- Enter the exponent (e) for powers, a whole number of 0 or more.
- Read a mod n, the sum, difference and product mod n, a to the power e mod n and the inverse of a.
- See the gcd of a and n and whether a and b are congruent mod n.
Formula
a mod n = a - n x floor(a / n), always from 0 to n - 1
(a x b) mod n = ((a mod n) x (b mod n)) mod n
a^e mod n by repeated squaring
inverse of a = x where a x x mod n = 1, found by the extended Euclid method, only when gcd(a, n) = 1
Numbers can have up to 60 digits, and every result is exact because the page uses whole-number arithmetic with no rounding.
Numbers modulo 97
For a = 38, b = 27 and n = 97: 38 mod 97 = 38, the sum is 65, the difference is 11 and the product is 1,026 mod 97 = 56. 38 to the power 45 mod 97 is 55, the inverse of 38 is 23 because 38 x 23 = 874 = 9 x 97 + 1, and a / b mod n is 38 x 27^-1 = 5.
For a = -17 and n = 12: -17 mod 12 = 7, while code that uses the remainder operator gives -5. For a = 48 and n = 18 the gcd is 6, so 48 has no inverse mod 18. Large inputs work too: 3 to the power 10^18 mod 10^20 + 39 is 41683252133234953438.
Remainders of negative numbers
In mathematics a mod n is always from 0 to n - 1, so -17 mod 12 is 7. Some programming languages return a remainder that takes the sign of the first number, so -17 % 12 gives -5. The page shows both, so you can compare them with the output of your own code.
When an inverse exists
The inverse of a mod n exists only when a and n share no factor other than 1. If gcd(a, n) is larger than 1, no multiple of a can leave a remainder of 1. Inverses are used to divide in modular arithmetic and are central to many cipher and checksum methods. The page also divides a by b mod n when b has an inverse.
Related number tools
Check factors with the Prime Number Calculator, count arrangements with the Combinations and Permutations Calculator, convert bases with the Number Base Converter, and use powers and logs in the Log, Exponent and Root Calculator.
Assumptions and limits
- a, b and e are whole numbers of up to 60 digits.
- The modulus is a whole number of 2 or more.
- Results use the non-negative remainder.
- Nothing is rounded, and nothing leaves your browser.
Frequently asked questions
What is 38 mod 97?
It is 38, since 38 is already less than 97. The result of a mod n is always from 0 up to n minus 1.
How do I find a modular inverse?
Use the extended Euclid method to find x with a x x mod n equal to 1. The inverse of 38 mod 97 is 23. It exists only when a and n share no factor above 1.
Why is -17 mod 12 equal to 7?
Because the remainder is always from 0 to 11. -17 equals -2 x 12 + 7. A programming language that gives -5 uses a remainder with the sign of the first number.
How can it compute huge powers so quickly?
It squares and reduces mod n at each step, so the numbers never grow past n squared. Even an exponent with 20 digits needs only about 70 steps.