What it means to work modulo n
Working modulo n means treating two numbers as the same whenever they differ by a multiple of n. A clock face is the everyday example: 15:00 and 3:00 are the same position because they differ by 12, and 27:00 would be too. The modulus is the size of the cycle, and reducing a number modulo n means finding where it lands on that cycle.
Formally, a ≡ b (mod n) means n divides a − b. The set of all integers congruent to a given value is a residue class, and there are exactly n of them: everything is congruent to one of 0, 1, …, n−1. Reducing a modulo n means naming which class it belongs to by giving that standard representative, called the least non-negative residue.
What makes this useful rather than merely tidy is that arithmetic survives the reduction. If a ≡ a′ and b ≡ b′ modulo n, then a+b ≡ a′+b′ and ab ≡ a′b′ too. So you may reduce whenever you like, before or after adding or multiplying, and the answer is the same. That is what lets you compute 17 × 8 modulo 5 as 2 × 3 = 6 ≡ 1 without ever forming 136, and it is why modular exponentiation of enormous numbers is tractable at all.
Subtraction survives too. Division does not, in general, and that exception is where most of the interesting structure lives.
Two conventions, and the bug that lives between them
The division algorithm says every pair (a, n) with n ≠ 0 has a unique quotient and remainder satisfying a = qn + r with 0 ≤ r < |n|. Getting that non-negative r requires the quotient to be the floor of a/n, rounded toward negative infinity.
Most programming languages do not do that. C, C++, Java, C# and JavaScript all truncate the quotient toward zero, which makes the remainder carry the sign of the dividend. So in those languages -17 % 5 is −2, not 3. Both satisfy a = qn + r; they differ in which of the two valid pairs they pick, because −17 = 5(−4) + 3 and −17 = 5(−3) − 2 are both true.
This is the source of a specific and very common defect. Code that wraps an index around a buffer, a circular list, a hue wheel or a day-of-week table works perfectly until the input goes negative, at which point it produces a negative index. The fix is the idiom ((a % n) + n) % n, which pushes the truncated remainder back into range without disturbing the already-correct positive case.
Not every language behaves this way. Python, Ruby and Haskell make the remainder take the sign of the divisor, so -17 % 5 is 3 there, matching the mathematical convention whenever the modulus is positive. Excel's MOD and SQL's MOD differ from each other on the same input. If you are porting a formula between environments, negative inputs are the first thing to test.
This calculator reports both: the least non-negative residue as the main answer, and the C-family truncated remainder beside it so the difference is visible. The reference table below shows the two side by side across the sign change.
Worked example: 17 mod 5, and (17 × 8) mod 5 the easy way
Reducing 17 modulo 5.
- Floor quotient. 17 ÷ 5 = 3.4, and the floor of that is 3.
- Remove that many whole moduli. 3 × 5 = 15.
- Residue. 17 − 15 = 2. It is in the range 0 to 4, as required.
So 17 ≡ 2 (mod 5), and the whole residue class is …, −8, −3, 2, 7, 12, 17, 22, … — every value differing from 17 by a multiple of 5.
Multiplying without the big number. To find (17 × 8) mod 5, reduce each operand first: 17 ≡ 2 and 8 ≡ 3. Then 2 × 3 = 6, and 6 ≡ 1 (mod 5). Check the long way: 17 × 8 = 136, and 136 = 5 × 27 + 1. ✓ The shortcut used numbers no larger than 6 to get an answer about 136, and the same idea scales: raising a 600-digit number to a 600-digit power modulo a 600-digit modulus is routine precisely because every intermediate stays below the modulus.
A power. Take 2⁴ mod 5. Squaring repeatedly: 2² = 4; 4² = 16 ≡ 1. So 2⁴ ≡ 1 (mod 5). That is Fermat's little theorem in action — for a prime p and any a not divisible by p, ap−1 ≡ 1 (mod p). With p = 5 the exponent is 4, and the theorem predicts the 1 before you compute it.
An inverse. The inverse of 2 modulo 5 is the value x with 2x ≡ 1. Testing: 2×1 = 2, 2×2 = 4, 2×3 = 6 ≡ 1. So the inverse is 3, and dividing by 2 modulo 5 means multiplying by 3. The extended Euclidean algorithm finds this directly rather than by search, which matters when the modulus has hundreds of digits.
Reading the outputs, and when division is possible
The residue names the class, not the number. Getting 2 from 17 mod 5 does not mean 17 has become 2; it means 17 sits in the class whose standard label is 2, alongside 7, 12, −3 and infinitely many others. That distinction matters when you interpret a result: a hash bucket of 2 tells you where an item goes, not what the item was.
The floor quotient tells you how many complete cycles were used. For 17 mod 5 it is 3, meaning three full laps and a partial one. In a date calculation that is the number of complete weeks; in a buffer it is how many times you wrapped.
The modular inverse exists exactly when gcd(a, n) = 1. This is the sharpest departure from ordinary arithmetic. Modulo 5, every non-zero value has an inverse because 5 is prime. Modulo 4, the value 2 has none: 2×0, 2×1, 2×2, 2×3 give 0, 2, 0, 2 and never 1. A modulus that is prime makes the residues a field, in which every non-zero element can be divided by; a composite modulus does not. That single fact explains why prime moduli dominate cryptography and error-correcting codes.
Watch the size of intermediate products. Reducing operands first keeps everything below the modulus, but the product of two values just under n is nearly n². Once n exceeds about 94 million, that product passes the point where whole numbers are stored exactly in double precision, and the answer can be silently wrong. This calculator warns at that threshold. Serious modular arithmetic uses big-integer libraries for exactly this reason.
The mathematical residue against the C-family remainder
| a | n | Floor quotient | a mod n (mathematical) | a % n (C, Java, JavaScript) |
|---|---|---|---|---|
| 17 | 5 | 3 | 2 | 2 |
| −17 | 5 | −4 | 3 | −2 |
| 100 | 7 | 14 | 2 | 2 |
| −100 | 7 | −15 | 5 | −2 |
| 0 | 9 | 0 | 0 | 0 |
| −1 | 12 | −1 | 11 | −1 |
| 7 | 12 | 0 | 7 | 7 |
| 25 | 25 | 1 | 0 | 0 |
The two columns agree for every non-negative a and differ for every negative a that is not an exact multiple. Python and Ruby produce the fourth column rather than the fifth when the modulus is positive.
Traps in modular arithmetic
- Assuming your language returns a non-negative remainder. Most do not. Wrap with
((a % n) + n) % nbefore using the result as an index. - Cancelling a common factor in a congruence. From 2x ≡ 2y (mod 6) you cannot conclude x ≡ y (mod 6); you get x ≡ y (mod 3). Cancellation is only valid after dividing the modulus by the gcd.
- Dividing without checking coprimality. There is no inverse of 2 modulo 4, so no meaning can be given to dividing by 2 there. Check gcd(a, n) = 1 first.
- Reducing an exponent modulo n. Exponents reduce modulo φ(n), not modulo n, and only when the base is coprime to n. Reducing an exponent the wrong way gives a plausible and wrong answer.
- Overflowing before reducing. Computing a×b and then taking the remainder can overflow even when the true modular product is small. Reduce first, and use big integers above about 94 million.
- Confusing the remainder with the quotient in a wrap-around. The residue says where on the cycle you landed; the floor quotient says how many complete cycles you used. Date and page-number calculations usually need both.
Where modular arithmetic actually shows up
Check digits. ISBN-13 and EAN barcodes weight the digits 1, 3, 1, 3, … and choose a final digit making the total ≡ 0 (mod 10). The IBAN standard reduces the rearranged account string modulo 97 and requires the result to be 1. Both catch single-digit errors and most transpositions, and both are pure modular arithmetic.
Calendars. Day-of-week calculations reduce a day count modulo 7, and leap-year rules reduce the year modulo 4, 100 and 400. The Gregorian rule is exactly three congruence tests combined.
Cryptography. RSA is modular exponentiation and nothing else: encryption is me mod n and decryption is cd mod n, with d the modular inverse of e modulo φ(n). Diffie-Hellman and elliptic-curve schemes are built on the same operations over carefully chosen moduli. The prime checker matters here because the security rests on the modulus being a product of large primes.
Hashing and cycling. Mapping a key into a table of size n is a modulo operation, and choosing n prime spreads keys more evenly when the inputs have structure. Circular buffers, ring counters and animation loops all wrap with the same operation.
The mathematical neighbours are close by. The residue is the r of the division algorithm, which shows the digit-by-digit working. Whether an inverse exists is a question for the greatest common factor, since the extended form of Euclid's algorithm produces the inverse as a by-product. Converting a number between bases is repeated reduction modulo the new base, which is what the base conversion calculator does. And solving simultaneous congruences with coprime moduli is the Chinese remainder theorem, which needs the least common multiple to state the period of the combined solution.