−17 mod 5
- Calculate
- Remainder a mod n
- Dividend a
- -17
- Divisor n
- 5
- Result
- 3
- Truncated remainder (sign of a)
- -2
- Euclidean remainder (never negative)
- 3
- Floored quotient ⌊a ÷ n⌋
- -4
Checked against: Independent calculation
Modulo calculator
Calculate a mod n under the floored, truncated and Euclidean conventions, modular powers a^b mod m of large numbers, and modular inverses, with steps.
By AdminDrafted with AI writing toolsUpdated Checked examples: 10
Result
Result: 3
- Truncated remainder (sign of a)
- −2
- Euclidean remainder (never negative)
- 3
- Floored quotient ⌊a ÷ n⌋
- −4
−17 ÷ 5 leaves 3 when the quotient is rounded down to −4 (Python, Excel MOD), but −2 when it is rounded toward zero to −3 (C, JavaScript %).
Where a sits between multiples of n
How it's calculated S
Divide
Floored remainder (sign of the divisor)
Python's %, Excel's MOD and most maths texts round the quotient down.
Truncated remainder (sign of the dividend)
C, Java and JavaScript's % round the quotient toward zero.
Euclidean remainder (never negative)
About the modulo calculator
The modulo operation a mod n gives the remainder left when a is divided by n. For positive numbers every convention agrees (17 mod 5 = 2), but for negative numbers they split: the floored remainder r = a − n⌊a/n⌋ takes the sign of the divisor, the truncated remainder rounds the quotient toward zero and takes the sign of the dividend, and the Euclidean remainder is never negative. The calculator shows all three, and also computes modular powers by square-and-multiply and modular inverses by the extended Euclidean algorithm.
Clock and calendar arithmetic, hashing and cyclic buffers all use remainders, and cryptography rests on modular powers. The default, −17 mod 5, is 3 under floored division (Python's %, Excel's MOD) but −2 under truncated division (the % of C and JavaScript). The textbook RSA example encrypts 65 as 65^17 mod 3233 = 2790.
Modular powers stay exact for exponents as large as 10^18 because every squaring is reduced mod m. An inverse a⁻¹ mod m exists only when gcd(a, m) = 1.
How to calculate a mod n
The value a mod n is the remainder left when a is divided by n. Divide, round the quotient down and subtract: a mod n = a − n⌊a/n⌋. For 17 mod 5, 17 = 3 × 5 + 2, so the answer is 2. Positive inputs give the same answer under every convention; negative ones do not.
Remainders of negative numbers
Every convention keeps a = n × q + r. They differ only in how the quotient q is rounded:
- Floored: q rounds down, and the remainder takes the sign of the divisor. Python's % and Excel's MOD work this way.
- Truncated: q rounds toward zero, and the remainder takes the sign of the dividend. The % operator in C, C++, Java and JavaScript works this way.
- Euclidean: the remainder is never negative; it runs from 0 up to, but not including, |n|.
For −17 mod 5, −17 ÷ 5 = −3.4. Floored division rounds that to −4, so r = −17 − 5 × (−4) = 3. Truncation rounds it to −3, so r = −17 − 5 × (−3) = −2.
| Dividend a | Divisor n | Floored remainder | Truncated remainder | Euclidean remainder |
|---|---|---|---|---|
| −17 | 5 | 3 | −2 | 3 |
| 17 | −5 | −3 | 2 | 2 |
| −17 | −5 | −2 | −2 | 3 |
| 7.5 | 2 | 1.5 | 1.5 | 1.5 |
| 1/3 | 1/5 | 2/15 | 2/15 | 2/15 |
When the floored and truncated remainders disagree, they differ by exactly |n|: 3 and −2 are 5 apart. The last two rows show that remainders work for decimals and fractions too: 1/3 = 1 × 1/5 + 2/15.
Python's expression reference documents its floored %, and Leijen's paper on division and modulus compares the conventions.
Getting the floored result in C or JavaScript
For a positive n, ((a % n) + n) % n turns a truncated remainder into the floored one: ((−17 % 5) + 5) % 5 = (−2 + 5) % 5 = 3. Excel's MOD(−17, 5) already returns 3 (Microsoft's MOD documentation).
Modular exponentiation: a^b mod m
Square-and-multiply never lets a number grow past m². Write the exponent in binary and start from 1. For each bit from left to right, square the running value, multiply by a if the bit is 1, and reduce mod m. For 4¹³ mod 497, 13 is 1101 in binary:
- Bit 1: 1² × 4 = 4.
- Bit 1: 4² × 4 = 64.
- Bit 0: 64² = 4,096, and 4,096 mod 497 = 120.
- Bit 1: 120² = 14,400, which is 484 mod 497. Then 484 × 4 = 1,936, which is 445 mod 497.
So 4¹³ mod 497 = 445, found without computing 4¹³ = 67,108,864. The same method handles exponents such as 10^18 exactly. A negative exponent uses the inverse: 3⁻² mod 11 = 4² mod 11 = 5, because 3⁻¹ mod 11 is 4.
Modular inverse
The inverse of a modulo m is the number x with a × x ≡ 1 (mod m), and it exists only when gcd(a, m) = 1. 3⁻¹ mod 11 = 4, because 3 × 4 = 12 = 11 + 1. 3⁻¹ mod 10 = 7, because 3 × 7 = 21 = 2 × 10 + 1.
6 has no inverse mod 15, because 6 and 15 share the factor 3. Multiples of 6 only ever leave remainders 0, 3, 6, 9 or 12 when divided by 15, never 1.
The extended Euclidean algorithm finds an inverse. For 3 mod 11: 11 = 3 × 3 + 2 and 3 = 1 × 2 + 1. Working back, 1 = 3 − 2 = 3 − (11 − 3 × 3) = 4 × 3 − 11, so the inverse is 4.
Everyday uses of mod
- Clock time: 15:00 is 3 o'clock, because 15 mod 12 = 3.
- Days of the week: 100 days after a Monday is a Wednesday, because 100 mod 7 = 2.
- Wrapping an index: position i in a list of length L wraps around as i mod L.
Common mistakes
- Assuming % means mod everywhere. −17 % 5 is 3 in Python but −2 in JavaScript.
- Testing for odd numbers with n % 2 == 1. In C, Java or JavaScript, −3 % 2 is −1, so the test misses negative odd numbers; n % 2 != 0 catches them.
- Dividing by zero. a mod 0 is undefined in every convention.
- Trusting floating-point remainders. In Python and JavaScript, 0.3 % 0.1 returns 0.09999999999999998, because neither number is exact in binary. Exact decimal arithmetic gives 0.
Input notes
- Remainders accept integers, decimals and fractions such as 1/3.
- Powers and inverses need whole numbers. The modulus must be positive, and at least 2 for an inverse.
- The modulus must stay below 2²⁰⁴⁸ and the exponent below 2⁴⁰⁹⁶.
To find common factors before looking for an inverse, use the GCD and LCM calculator. For weekday questions, use the day of the week calculator.
Worked examples
17 mod −5
- Calculate
- Remainder a mod n
- Dividend a
- 17
- Divisor n
- -5
- Result
- -3
- Truncated remainder (sign of a)
- 2
- Euclidean remainder (never negative)
- 2
Checked against: Euclidean 17 − 5·⌊17/5⌋ = 2
7.5 mod 2
- Calculate
- Remainder a mod n
- Dividend a
- 7.5
- Divisor n
- 2
- Result
- 1.5
- Truncated remainder (sign of a)
- 1.5
Checked against: 7.5 % 2 = 1.5
4^13 mod 497
- Calculate
- Power a^b mod m
- Base a
- 4
- Exponent b
- 13
- Modulus m
- 497
- Result
- 445
Checked against: Wikipedia — Modular exponentiation worked example
Questions
How do you calculate a mod n?
Divide, round the quotient down, and subtract: a mod n = a − n⌊a/n⌋. For 17 mod 5, 17 ÷ 5 = 3.4, which rounds down to 3, and 17 − 5 × 3 = 2. For −17 mod 5, −3.4 rounds down to −4, and −17 − 5 × (−4) = 3. On a 12-hour clock, 15:00 is 15 mod 12 = 3 o'clock.
Why do Python and JavaScript give different answers for a negative modulo?
They round the quotient differently. Python's % floors it, so −17 % 5 = 3, with the sign of the divisor; JavaScript, C and Java truncate toward zero, so −17 % 5 = −2, with the sign of the dividend. Both satisfy a = n × q + r. Excel's MOD matches Python. In JavaScript, ((a % n) + n) % n gives the floored answer when n is positive.
How do you calculate large powers modulo a number?
Use square-and-multiply: write the exponent in binary, square repeatedly, and reduce mod m after every step so the numbers never grow past m². For 4^13 mod 497, 13 is 1101 in binary and the answer is 445, the same as Python's pow(4, 13, 497). Computing 4^13 = 67,108,864 first works here, but not for exponents like 10^18.
What is a modular inverse?
The inverse of a modulo m is the number x with a × x ≡ 1 (mod m). 3⁻¹ mod 11 = 4 because 3 × 4 = 12 = 11 + 1. It exists only when gcd(a, m) = 1, so 2 has no inverse mod 10. The extended Euclidean algorithm finds it; in the textbook RSA example the private key 2753 is the inverse of 17 mod 3120, since 17 × 2753 = 46,801 = 15 × 3120 + 1.
What is the difference between remainder and modulo?
For positive numbers they agree: 17 divided by 5 leaves 2 either way. For negative numbers the remainder in the C and JavaScript sense follows the sign of the dividend (−17 rem 5 = −2), while modulo in the mathematical sense follows the divisor or is never negative (−17 mod 5 = 3). When the two differ, they differ by exactly |n|.
About this calculator
Sources
- Knuth, The Art of Computer Programming Vol. 1, §1.2.4 (mod) and Vol. 2, §4.6.3 (powers)
- Leijen (2001), Division and modulus for computer scientists
- Wikipedia — Modular exponentiation (4^13 mod 497 example)
- Microsoft Excel MOD function
Checked against references
This calculator includes 10 worked examples with independently sourced answers. They run in the test suite, and you can run them here too.