Saved

Press the star next to a tool's name to save it.

All my tools

Modular Arithmetic Calculator

Use this modular arithmetic calculator for mod, congruences, powers mod n, modular inverses, linear congruences, the Chinese remainder theorem and Fermat's little theorem.

Restored your last values ·

Choose a job and enter a, the modulus n, and what that job needs: b for congruence, sums and linear congruences, the exponent e for powers. For the Chinese remainder theorem, type one congruence per line as the remainder and then the modulus. Numbers can be negative or very long.

Everything is worked out in your browser. Nothing you type is sent anywhere.

–

–

Choose what you want, enter your numbers, then press Calculate.

A modular arithmetic calculator does the calculations of clock arithmetic: remainders, congruences, sums and products mod n, powers mod n, modular inverses, systems of congruences with the Chinese remainder theorem, linear congruences, and a check of Fermat's little theorem. Choose the job, enter the numbers and press the button. The rules follow the Wikipedia pages on modular arithmetic, the modulo operation, modular exponentiation, modular multiplicative inverses and the extended Euclidean algorithm, and the work is done in your browser with exact arithmetic. It covers the inverse modulo, the Chinese remainder and the Fermat's little theorem calculators.

How to use the modular arithmetic calculator

  1. Choose what you want.
  2. Enter a and the modulus n, and the other numbers that the job needs.
  3. For the Chinese remainder theorem, type one congruence per line.
  4. Press Calculate.

Congruence and remainders

The page defines a and b as congruent modulo n when their difference is a multiple of n. For instance, 38 and 14 are congruent mod 12, because 38 minus 14 is 24, which is 2 times 12. The definition also works with negative numbers: 2 and −3 are congruent mod 5. The value a mod n is the unique remainder r from 0 up to n − 1 that is congruent to a. For negative a, programming languages differ, as the modulo page explains: the truncated remainder takes the sign of a, the floored remainder takes the sign of n, and the Euclidean remainder is never negative. For −7 mod 3, the calculator gives 2, the floored value is 2 and the truncated value is −1.

Sums, differences and products

Addition, subtraction and multiplication can be done on the remainders. The page's examples: 7 + 8 is congruent to 3 mod 12, and 2 × 8 is congruent to 4 mod 12. The calculator shows the plain result and the reduced result.

Modular exponentiation

Computing a to the power e mod n by multiplying e times is slow for large e. The page describes the square and multiply method, which uses the binary digits of e. For 4 to the power 13 mod 497, the exponent 13 is 1101 in binary. The running result is 4, then 30, then 445, and 445 is the answer. The direct value 4 to the power 13 is 67,108,864, and its remainder mod 497 is also 445. The calculator uses this method, so it handles huge exponents quickly, and for small ones it lists the multiplications. A negative exponent uses the inverse of a.

Modular inverse

The inverse of a mod n is a number x with a times x congruent to 1. The page states that it exists exactly when a and n have no common factor, and then it is unique mod n. It is found with the extended Euclidean algorithm, which writes the greatest common divisor as a combination of the two numbers. The page's example is the inverse of 15 mod 34, which is −9, or 25: 15 times 25 is 375, and 375 is 11 times 34 plus 1. The calculator shows this combination and the check. For 4 mod 10, which share a factor of 2, there is no inverse.

Linear congruences

To solve a times x congruent to b mod n, let d be the greatest common divisor of a and n. There are solutions only when d divides b, and then there are exactly d of them. The page gives the examples 3x ≡ 1 (mod 10), which has the single solution x = 7; 4x ≡ 5 (mod 10), which has none; and 4x ≡ 6 (mod 10), which has two, x = 4 and x = 9. The calculator lists all of them.

The Chinese remainder theorem

The theorem solves several congruences at once. The page's example is x ≡ 4 mod 5, x ≡ 4 mod 7 and x ≡ 6 mod 11, with the solution x ≡ 39 mod 385. Type the lines 4 5, 4 7 and 6 11 to see this. The calculator also handles moduli that are not coprime, and tells you when the congruences contradict each other, such as x ≡ 1 mod 4 and x ≡ 2 mod 6.

Fermat's little theorem

Fermat's little theorem says that, for a prime n and a not divisible by n, a to the power n − 1 is congruent to 1 mod n. It also gives the inverse: a to the power n − 2 is the inverse of a. For a = 3 and n = 7, 3 to the power 6 mod 7 is 1, and 3 to the power 5 mod 7 is 5, the inverse of 3. The calculator tests whether n is prime and shows whether the theorem holds. If it fails, n must be composite. A composite n for which it holds anyway, such as 341 with base 2, is called a pseudoprime.

Typing tips

The numbers can be negative, and very long numbers are handled exactly. Leave the boxes that your chosen job does not use empty. For the Chinese remainder theorem, you can separate the lines with semicolons if you prefer.

Checking an answer

To check a remainder, multiply the quotient by n and add the remainder: you must get a back. To check an inverse, multiply it by a and reduce mod n: the result must be 1.

Common mistakes

  • Expecting a negative remainder. The standard remainder lies from 0 to n − 1.
  • Looking for an inverse when a and n share a factor. None exists.
  • Assuming Fermat's test proves primality. It only proves compositeness.
  • Computing aᵉ first and reducing afterward. Reduce at each step instead.
  • Using moduli that clash in the Chinese remainder theorem. They may have no solution.

What next

Use this often? Add Modular Arit to your Home screen.

Frequently asked questions

What is a modular arithmetic calculator?

A tool for clock arithmetic: remainders, congruences, powers and inverses mod n, and systems of congruences.

How do you find a modular inverse?

Use the extended Euclidean algorithm. The inverse of 15 mod 34 is 25, because 15 × 25 = 375 = 11 × 34 + 1.

What is the Chinese remainder theorem?

It solves several congruences with different moduli together. x ≡ 4 (mod 5), 4 (mod 7), 6 (mod 11) gives x ≡ 39 (mod 385).

How do you compute a power mod n quickly?

Use square and multiply on the binary digits of the exponent. 4¹³ mod 497 = 445.

What is Fermat's little theorem?

If n is prime and does not divide a, then aⁿ⁻¹ ≡ 1 (mod n). For a = 3 and n = 7, 3⁶ mod 7 = 1.

What went wrong?

We only receive the reason you pick, never what you typed into the tool.

Thanks for your feedback.

More Math Tools