Modulo Calculator
Remainders under all three conventions, modular powers, inverses, congruences and CRT.
Try before you buy.
- Free preview: the names of each table’s first rows (up to 3) for your numbers, with the answer, its working and every other figure hidden.
- Locked until you unlock it: download and copy.
- Unlock: Pro pass, ₹179 for 30 days or ₹79 for 1 week, a one-time payment unless you choose automatic renewal. Unlock: Pro pass, $5.99 for 30 days or $2.99 for 1 week, a one-time payment unless you choose automatic renewal.
Ways to unlock shows how to get the full result.
Printing this result is locked in the free preview.
Result
This is the last answer worked out. Fix the input above to update it.
Step by step
Locked in the free preview. Opens the ways to unlock this result.
Locked in the free preview. Batch runs unlock with a pass.
Locked in the free preview. Query results unlock with a pass.
About the Modulo Calculator
Work out a mod n, the remainder when a is divided by n, exactly: for whole numbers with thousands of digits, for decimals and for fractions, under each of the three conventions programming languages use: floored (Python, Excel), truncated (C, Java, JavaScript) and Euclidean (never negative). Each answer comes with its quotient, the identity a = n × q + r and every step.
Four more modes cover the rest of modular arithmetic: modular exponentiation a^e mod n by repeated squaring, with a table of every square and a Fermat or Euler check; the modular inverse a⁻¹ mod n by the extended Euclidean algorithm; linear congruences ax ≡ b (mod n) with all of their solutions; and systems of congruences by the Chinese remainder theorem, also when the moduli share factors. The working is done in your browser.
How to use it
- Choose what to work out: a mod n, Power, Inverse, ax ≡ b or Chinese remainder.
- Type the numbers. Whole numbers can have up to 5,000 digits or be expressions such as
2^64 - 1or10!, and 0x, 0b or 0o in front reads one in hex, binary or octal (0xFF); a mod n also takes decimals and fractions. You can paste a whole problem such as17 mod 5,3^200 mod 13or3x ≡ 4 (mod 7)into the first box and it is split into the right fields. - For a mod n, choose the convention of the headline answer; the table always shows all three.
- Read the answer, the steps and the check. With a pass, or after unlocking this result, copy the whole working or download it as a text file.
Examples
−17 mod 5
floored 3 · truncated −2 · Euclidean 3
Python gives -17 % 5 = 3; C, Java and JavaScript give −2.
4^13 mod 497
445
13 = 1101₂, so 4¹³ = 4 × 4⁴ × 4⁸ ≡ 4 × 256 × 429 ≡ 445 (mod 497).
17⁻¹ mod 3120
2753
17 × 2,753 = 46,801 = 15 × 3,120 + 1.
6x ≡ 4 (mod 10)
x ≡ 4 (mod 5), that is x = 4 or 9 modulo 10
gcd(6, 10) = 2 divides 4, so there are 2 solutions modulo 10.
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
x ≡ 23 (mod 105)
The classic problem of the Sunzi Suanjing.
7.5 mod 2
1.5
7.5 = 2 × 3 + 1.5.
Common uses
- Checking number theory, discrete mathematics and cryptography homework step by step.
- Seeing why % gives different answers for negative numbers in Python and in C, Java or JavaScript.
- Working through RSA and Diffie–Hellman examples: modular powers and inverses with every step shown.
- Solving calendar, scheduling and “remainder” puzzles with the Chinese remainder theorem.
Floored, truncated and Euclidean remainders
Every convention keeps a = n × q + r with |r| < |n|. They differ in how the quotient q is rounded when a ÷ n is negative (Boute, “The Euclidean definition of the functions div and mod”):
- Floored: q = ⌊a ÷ n⌋, so r is 0 or has the sign of n. This is the definition of mod in Knuth’s The Art of Computer Programming (Vol. 1, §1.2.4), and what Python’s %, Excel’s MOD and Java’s Math.floorMod give: −17 mod 5 = 3.
- Truncated: q is a ÷ n with its fractional part dropped, so r is 0 or has the sign of a. This is the % of C since C99, Java, JavaScript and Rust: −17 % 5 = −2.
- Euclidean: q is chosen so that 0 ≤ r < |n| whatever the signs, as with Dart’s %: −17 mod 5 = 3 and 17 mod −5 = 2.
When a and n are both positive, all three agree.
Modular exponentiation by repeated squaring
To find a^e mod n without ever writing out a^e, write e in binary, square a again and again (a, a², a⁴, a⁸, …) reducing modulo n after every step, and multiply together the squares where e has a 1 bit: for e = 13 = 1101₂ that is a × a⁴ × a⁸. The work grows with the number of binary digits of e, not with e itself, so exponents with hundreds of digits take a moment.
When gcd(a, n) = 1, Euler’s theorem a^φ(n) ≡ 1 (mod n), or Fermat’s little theorem a^(n−1) ≡ 1 (mod n) when n is prime, gives the same answer from a smaller exponent, and the tool shows that check as well.
Inverses, congruences and the Chinese remainder theorem
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: every row of its table keeps r = s × n + t × a, so the row where r = 1 gives 1 = s × n + t × a, and t reduced modulo n is the inverse.
The congruence ax ≡ b (mod n) has a solution exactly when d = gcd(a, n) divides b. Dividing by d and multiplying by an inverse gives one solution x₀, and the d solutions modulo n are x₀, x₀ + n/d, x₀ + 2n/d and so on.
For a system x ≡ aᵢ (mod nᵢ) whose moduli have no common factor in pairs, the Chinese remainder theorem gives exactly one solution modulo N = n₁ × n₂ × ⋯: x = Σ aᵢNᵢyᵢ, where Nᵢ = N ÷ nᵢ and yᵢ is the inverse of Nᵢ modulo nᵢ (Knuth, The Art of Computer Programming, Vol. 2, §4.3.2). When moduli share a factor, the congruences are combined two at a time: a pair agrees exactly when the gcd of its moduli divides the difference of its remainders, and the two combine into one congruence modulo their least common multiple.
Limitations
- Numbers, exponents included, can have up to 5,000 digits (a 5,000-digit exponent has about 16,600 binary digits). Very long exponents with very long moduli can take many seconds; a calculation stops after 30 seconds, and Stop ends it sooner.
- Tables list up to 2,000 rows (fewer when the numbers in them are very long); the answer and the check always use every step.
- Powers, inverses, congruences and systems need whole numbers. Only a mod n takes decimals and fractions.
- The Euler check is shown for moduli up to 10¹², because φ(n) needs the prime factors of n; for prime moduli of up to 300 digits the Fermat check is used. Primes above about 3.3 × 10²⁴ are confirmed with the Baillie–PSW probable-prime test, which has no known counterexample.
Privacy
On this device: nothing is sent
Everything happens in your browser. What you enter or open here is not uploaded or stored by MySmartCoPilot.
Frequently asked questions
What do I get without a pass?
Without a pass, Modulo Calculator shows the names of each table’s first rows (up to 3) for your numbers, with the answer, its working and every other figure hidden. Until you unlock it, the result can’t be downloaded or copied. A Pro, Premium or Ultimate pass, a one-time payment unless you choose automatic renewal, unlocks the full result. The pricing page lists the passes and their prices.
Why do Python and JavaScript give different answers for −7 % 3?
They round the quotient differently. Python’s % is floored: −7 ÷ 3 = −2.33… is rounded down to q = −3, so r = −7 − 3 × (−3) = 2. JavaScript’s % is truncated: q = −2, so r = −7 − 3 × (−2) = −1. Both satisfy −7 = 3q + r; choose the convention in the tool that matches your language.
Can a mod n be negative?
Under the floored rule the remainder has the sign of n, so it is negative only when n is negative: 17 mod −5 = −3. Under the truncated rule it has the sign of a: −17 % 5 = −2. The Euclidean remainder is never negative.
How do I find the inverse of a number modulo n?
Run the extended Euclidean algorithm on n and a. If the last remainder before 0 (the gcd) is 1, the row with remainder 1 gives 1 = s × n + t × a, so a × t ≡ 1 (mod n), and t reduced modulo n is the inverse. For 17 modulo 3,120, t = −367 and the inverse is −367 + 3,120 = 2,753. If the gcd is not 1, there is no inverse.
How is 3^200 mod 13 worked out without a 96-digit number?
By repeated squaring: 3, 3² = 9, 3⁴ = 81 ≡ 3, 3⁸ ≡ 9 and so on, each reduced modulo 13, and then the squares for the 1 bits of 200 = 11001000₂ are multiplied together. Fermat’s little theorem is quicker here: 3¹² ≡ 1 (mod 13) and 200 = 16 × 12 + 8, so 3²⁰⁰ ≡ 3⁸ ≡ 9 (mod 13).
What does the Chinese remainder theorem say?
If no two of the moduli n₁, n₂, … have a common factor, then for any remainders a₁, a₂, … there is exactly one x modulo n₁ × n₂ × ⋯ with x ≡ aᵢ (mod nᵢ) for every i. For x ≡ 2 (mod 3), x ≡ 3 (mod 5) and x ≡ 2 (mod 7) it is x ≡ 23 (mod 105).