Modulo Calculator
−17 mod 5 = 3 (mathematical) or −2 (truncated). Mathematical: −17 = (−4) × 5 + 3. Truncated: −17 = (−3) × 5 + (−2). In mathematics the remainder takes the sign of n (floor division), so −17 mod 5 = 3; the truncated remainder of JavaScript’s % takes the sign of a and gives −2. For positive numbers they agree: 17 mod 5 = 2. This calculator works out a mod n for whole numbers of up to 200 digits, shows both conventions side by side with the quotient and the check a = q × n + r, and tests a ≡ b (mod n), for example 38 ≡ 14 (mod 12): yes. It also computes a^b mod n by square-and-multiply with exponents of up to 200 digits, for example 7^222 mod 10 = 9, and the modular inverse with the extended Euclidean algorithm and its Bézout coefficients, for example 3⁻¹ mod 11 = 4, or explains why none exists: 6 has no inverse mod 15. n = 0 and non-integers are rejected with a message.
Updated Runs in your browser: nothing you enter is uploadedHow this tool works
−17 mod 5 = 3 (mathematical) or −2 (truncated)
Mathematical: −17 = (−4) × 5 + 3. Truncated: −17 = (−3) × 5 + (−2).
| Measure | Mathematical (floor) | Truncated (like JS %) |
|---|---|---|
| Quotient rounds | down (floor) | toward zero |
| Quotient q | −4 | −3 |
| Remainder r | 3 | −2 |
| Sign of r | same as n (or 0) | same as a (or 0) |
| Check a = q × n + r | −17 = (−4) × 5 + 3 | −17 = (−3) × 5 + (−2) |
- Least non-negative residue
- 3
- Does n divide a?
- No
The working
- −17 ÷ 5 is not a whole number: it lies between −4 and −3.
- Mathematical convention: round the quotient down, q = ⌊a ÷ n⌋ = −4, so r = a − q × n = −17 − (−4) × 5 = 3. The remainder has the sign of n, and 0 ≤ |r| < |n|.
- Truncated convention: round the quotient toward zero, q = −3, so r = −17 − (−3) × 5 = −2. The remainder has the sign of a (this is what % does in JavaScript).
- They differ here: −17 ÷ 5 is negative and not a whole number, so rounding down goes one step further than rounding toward zero. The quotients differ by 1 and the remainders by n: 3 − (−2) = 5.
- The least non-negative residue, −17 mod 5 = 3, is the one clock arithmetic and congruences use.
Remainders of 0 to 20 divided by 2 to 12
| a | mod 2 | mod 3 | mod 4 | mod 5 | mod 6 | mod 7 | mod 8 | mod 9 | mod 10 | mod 11 | mod 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 1 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 4 | 0 | 1 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 5 | 1 | 2 | 1 | 0 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
| 6 | 0 | 0 | 2 | 1 | 0 | 6 | 6 | 6 | 6 | 6 | 6 |
| 7 | 1 | 1 | 3 | 2 | 1 | 0 | 7 | 7 | 7 | 7 | 7 |
| 8 | 0 | 2 | 0 | 3 | 2 | 1 | 0 | 8 | 8 | 8 | 8 |
| 9 | 1 | 0 | 1 | 4 | 3 | 2 | 1 | 0 | 9 | 9 | 9 |
| 10 | 0 | 1 | 2 | 0 | 4 | 3 | 2 | 1 | 0 | 10 | 10 |
| 11 | 1 | 2 | 3 | 1 | 5 | 4 | 3 | 2 | 1 | 0 | 11 |
| 12 | 0 | 0 | 0 | 2 | 0 | 5 | 4 | 3 | 2 | 1 | 0 |
| 13 | 1 | 1 | 1 | 3 | 1 | 6 | 5 | 4 | 3 | 2 | 1 |
| 14 | 0 | 2 | 2 | 4 | 2 | 0 | 6 | 5 | 4 | 3 | 2 |
| 15 | 1 | 0 | 3 | 0 | 3 | 1 | 7 | 6 | 5 | 4 | 3 |
| 16 | 0 | 1 | 0 | 1 | 4 | 2 | 0 | 7 | 6 | 5 | 4 |
| 17 | 1 | 2 | 1 | 2 | 5 | 3 | 1 | 8 | 7 | 6 | 5 |
| 18 | 0 | 0 | 2 | 3 | 0 | 4 | 2 | 0 | 8 | 7 | 6 |
| 19 | 1 | 1 | 3 | 4 | 1 | 5 | 3 | 1 | 9 | 8 | 7 |
| 20 | 0 | 2 | 0 | 0 | 2 | 6 | 4 | 2 | 0 | 9 | 8 |
Eight worked examples
| Problem | Working | Answer |
|---|---|---|
| 17 mod 5 | 17 = 3 × 5 + 2 | 2 |
| −17 mod 5 | Floor: −17 = (−4) × 5 + 3. Truncated: −17 = (−3) × 5 + (−2). | 3 (mathematical), −2 (truncated) |
| Is 38 ≡ 14 (mod 12)? | 38 − 14 = 24 = 2 × 12, a multiple of 12. | Yes |
| Is 38 ≡ 15 (mod 12)? | 38 − 15 = 23 is not a multiple of 12: dividing leaves 11. | No |
| Last digit of 7^222 (7^222 mod 10) | 8 bits: 7 squarings and 5 multiplications | 9 |
| 2^1000 mod 13 | 10 bits: 9 squarings and 5 multiplications | 3 |
| Inverse of 3 mod 11 | 1 = 4 × 3 + (−1) × 11 | 4 |
| Inverse of 6 mod 15 | 3 = (−2) × 6 + 1 × 15, so gcd(6, 15) = 3, not 1 | No inverse |
Negative numbers: mathematical and truncated remainders
| a | n | Floor q | Floor r | Truncated q | Truncated r | Least non-negative residue |
|---|---|---|---|---|---|---|
| 17 | 5 | 3 | 2 | 3 | 2 | 2 |
| −17 | 5 | −4 | 3 | −3 | −2 | 3 |
| 17 | −5 | −4 | −3 | −3 | 2 | 2 |
| −17 | −5 | 3 | −2 | 3 | −2 | 3 |
| −1 | 12 | −1 | 11 | 0 | −1 | 11 |
| −100 | 7 | −15 | 5 | −14 | −2 | 5 |
| −15 | 5 | −3 | 0 | −3 | 0 | 0 |
| 0 | 5 | 0 | 0 | 0 | 0 | 0 |
Days of the week as numbers mod 7, starting on a Wednesday
| Days from today | Calculation | Remainder mod 7 | Day of the week |
|---|---|---|---|
| 1 later | 3 + 1 = 4; 4 mod 7 | 4 | Thursday |
| 2 later | 3 + 2 = 5; 5 mod 7 | 5 | Friday |
| 7 later | 3 + 7 = 10; 10 mod 7 | 3 | Wednesday |
| 10 later | 3 + 10 = 13; 13 mod 7 | 6 | Saturday |
| 30 later | 3 + 30 = 33; 33 mod 7 | 5 | Friday |
| 100 later | 3 + 100 = 103; 103 mod 7 | 5 | Friday |
| 365 later | 3 + 365 = 368; 368 mod 7 | 4 | Thursday |
| 1000 later | 3 + 1000 = 1003; 1003 mod 7 | 2 | Tuesday |
| 1 ago | 3 − 1 = 2; 2 mod 7 | 2 | Tuesday |
| 10 ago | 3 − 10 = −7; −7 mod 7 | 0 | Sunday |
| 100 ago | 3 − 100 = −97; −97 mod 7 | 1 | Monday |
Clock arithmetic on a 12-hour clock
| Start (o’clock) | Hours later | Sum | Sum mod 12 | The clock shows |
|---|---|---|---|---|
| 9 | 5 | 14 | 2 | 2 |
| 9 | 3 | 12 | 0 | 12 |
| 11 | 2 | 13 | 1 | 1 |
| 12 | 7 | 19 | 7 | 7 |
| 3 | 15 | 18 | 6 | 6 |
| 6 | 24 | 30 | 6 | 6 |
| 10 | 100 | 110 | 2 | 2 |
| 9 | −12 | −3 | 9 | 9 |
Modular inverses mod 12 and mod 7
| a | gcd(a, 12) | Inverse mod 12 | gcd(a, 7) | Inverse mod 7 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | none | 1 | 4 |
| 3 | 3 | none | 1 | 5 |
| 4 | 4 | none | 1 | 2 |
| 5 | 1 | 5 | 1 | 3 |
| 6 | 6 | none | 1 | 6 |
| 7 | 1 | 7 | 7 | none |
| 8 | 4 | none | 1 | 1 |
| 9 | 3 | none | 1 | 4 |
| 10 | 2 | none | 1 | 5 |
| 11 | 1 | 11 | 1 | 2 |
Last digits of powers (a^k mod 10)
| a | a¹ | a² | a³ | a⁴ | Last digit repeats | Last digit of a¹⁰⁰ |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | every power (it never changes) | 0 |
| 1 | 1 | 1 | 1 | 1 | every power (it never changes) | 1 |
| 2 | 2 | 4 | 8 | 6 | every 4 powers | 6 |
| 3 | 3 | 9 | 7 | 1 | every 4 powers | 1 |
| 4 | 4 | 6 | 4 | 6 | every 2 powers | 6 |
| 5 | 5 | 5 | 5 | 5 | every power (it never changes) | 5 |
| 6 | 6 | 6 | 6 | 6 | every power (it never changes) | 6 |
| 7 | 7 | 9 | 3 | 1 | every 4 powers | 1 |
| 8 | 8 | 4 | 2 | 6 | every 4 powers | 6 |
| 9 | 9 | 1 | 9 | 1 | every 2 powers | 1 |
How to calculate a mod n
- Divide a by n and round the quotient. Find q so that a = q × n + r. For 17 ÷ 5 the quotient is 3 and 17 = 3 × 5 + 2, so 17 mod 5 = 2.
- Choose the convention for a negative number. Rounding down (floor) gives −17 = (−4) × 5 + 3, so −17 mod 5 = 3. Rounding toward zero (truncated) gives −17 = (−3) × 5 + (−2), so the remainder is −2. The calculator shows both.
- Test a congruence by the remainder or the difference. a ≡ b (mod n) when a and b leave the same remainder, or when n divides a − b. 38 − 14 = 24 = 2 × 12, a multiple of 12.
- Use square-and-multiply for a power. Do not compute a^b first. Square the running result mod n for every bit of b, and multiply by a when the bit is 1. 7^222 mod 10 = 9 takes 7 squarings and 5 multiplications.
- Find an inverse with the extended Euclidean algorithm. Run Euclid’s algorithm on n and a while tracking coefficients. If gcd(a, n) = 1 the coefficient of a is the inverse: 1 = 4 × 3 + (−1) × 11 gives 3⁻¹ mod 11 = 4. If the gcd is larger there is no inverse.
Frequently asked questions
- What does mod mean and what is 17 mod 5?
- a mod n is the remainder left when a is divided by n. 17 mod 5 = 2 because 17 = 3 × 5 + 2: five goes into 17 3 times with 2 left over. The remainder is always smaller than n in size, so a mod 5 is one of five values, and the table above lists a mod n for every a from 0 to 20 and n from 2 to 12.
- How do you calculate the modulo of a negative number?
- Divide, round the quotient, and take what is left. In the mathematical convention the quotient is rounded down, so −17 ÷ 5 gives q = −4 and −17 = (−4) × 5 + 3: −17 mod 5 = 3. A shortcut is to add the divisor until the number is positive: −17 + 4 × 5 = 3, and 3 mod 5 = 3. With a truncated remainder the result is −2 instead.
- Why is −17 mod 5 equal to 3 in one place and −2 in another?
- Both are correct remainders of the same division; they differ only in how the quotient is rounded. Floor division uses q = −4, which gives r = 3 with the sign of n. Truncated division rounds toward zero, q = −3, which gives r = −2 with the sign of a. The two always differ by exactly n (3 − (−2) = 5) and only when a and n have opposite signs and a is not a multiple of n. Python’s % follows the floor convention (−17 % 5 is 3) while JavaScript’s % is truncated (−17 % 5 is −2); for other languages, check their documentation before relying on the sign. This calculator always shows both.
- What does a ≡ b (mod n) mean and how do I test it?
- It says a and b are congruent modulo n: they differ by a multiple of n, which is the same as leaving the same remainder when divided by n. To test it, compute a − b and check that n divides it, or compare a mod n with b mod n. 38 − 14 = 24 = 2 × 12, a multiple of 12. 38 − 15 = 23 is not a multiple of 12: dividing leaves 11. Congruence modulo n and modulo −n mean the same thing.
- How can a^b mod n be found when b has 200 digits?
- By square-and-multiply, also called binary exponentiation. Write b in binary and walk through its bits: square the running result mod n, and when the bit is 1 multiply by a mod n. Every number stays below n, so nothing huge is ever built. A 200-digit exponent has at most 665 bits, so it needs at most 664 squarings and 664 multiplications, instead of an impossible count of repeated multiplications. For example 7^222 mod 10 = 9 needs 7 squarings and 5 multiplications instead of 221.
- What is a modular inverse and when does it exist?
- The inverse of a modulo n is a number x with a × x ≡ 1 (mod n), written a⁻¹. It exists exactly when gcd(a, n) = 1. 3⁻¹ mod 11 = 4, because 3 × 4 = 12 = 1 × 11 + 1. 6 has no inverse mod 15: No inverse because gcd(6, 15) = 3, not 1. Mod 12 only 1, 5, 7, 11 have an inverse, and mod a prime every non-zero a has one.
- How does the extended Euclidean algorithm give the inverse?
- Euclid’s algorithm finds gcd(a, n) by repeated division; the extended version tracks coefficients so each remainder is written as s × a + t × n. When the last non-zero remainder is 1, that equation reads 1 = s × a + t × n, and taking it mod n removes the t × n term, leaving s × a ≡ 1. For 3 mod 11 the identity is 1 = 4 × 3 + (−1) × 11, so the inverse is 4. For 17 mod 3120 it is 1 = (−367) × 17 + 2 × 3120; the coefficient is negative, so it is brought into range: 2753. The numbers s and t are the Bézout coefficients.
- What is clock arithmetic?
- It is arithmetic mod 12 on a clock face (or mod 7 on a week, or mod 24 on a day): you add as usual and then wrap around. Five hours after 9 o’clock is 14, and 14 mod 12 = 2, so the clock shows 2. Days of the week work the same way mod 7: counting Sunday as 0, Wednesday is 3, so 100 days later is (3 + 100) mod 7 = 5, a Friday, and 10 days ago is (3 − 10) mod 7 = 0, a Sunday. The negative case is why clocks and calendars use the mathematical convention: for a positive n it never gives a negative remainder.
- Why can n not be 0, and what is mod 1?
- a mod 0 would divide by zero, which has no value, so the calculator asks for another n. Mod 1 is allowed and trivial: every integer is a multiple of 1, so a mod 1 = 0 for every a, every power is 0 and the inverse of any a mod 1 is 0, as in Python.
- Can I take a modulo of a decimal or a fraction?
- The calculator accepts whole numbers only. Remainders of decimals exist as a different operation (a floating-point remainder), and they bring rounding errors that congruences and inverses cannot tolerate. Typing 5.5, 1/2 or 1e3 gives a message instead of a result; 5.0 is read as 5.
- Is a negative exponent allowed in a^b mod n?
- Yes, when a has an inverse mod n. a^(−k) means (a⁻¹)^k, so 3^(−2) mod 11 = 5: the inverse of 3 mod 11 is 4 and 4² mod 11 = 5. If gcd(a, n) is not 1 the calculator says the power has no value. A base of 0 with exponent 0 is taken as 1, as in Python.
- What is modulo used for?
- Clock and calendar arithmetic; hash tables, which store a key at (hash mod table size); check digits, such as the last digit of an ISBN-13 or a Luhn-checked card number, which are chosen so a sum is 0 mod 10; the Gregorian leap-year rule (divisible by 4, except multiples of 100 that are not multiples of 400): 2100 has mod 4 = 0, mod 100 = 0 and mod 400 = 100, so it is not a leap year, while 2024 has mod 4 = 0, mod 100 = 24 and mod 400 = 24, so it is; and public-key cryptography, where modular exponentiation and inverses are the core operations. As a toy RSA example, n = 61 × 53 = 3233 and (61 − 1) × (53 − 1) = 3120; encrypting 65 with exponent 17 gives 65^17 mod 3233 = 2790, the inverse of 17 mod 3120 is 2753, and raising 2790 to that power mod 3233 gives back 65. Real keys are hundreds of digits long, which is why the calculator accepts 200-digit inputs.
- How large can the numbers be?
- Each of a, b and n may have up to 200 digits, with an optional minus sign. All arithmetic is exact BigInt arithmetic, so there is no rounding at any size. Longer inputs are rejected with a message that gives their digit count. In the working, long numbers are shortened to their first and last digits while the result rows show every digit.
How it works
Input: whole numbers with an optional sign, typed with digits only (thousands separators such as 1,000 and a zero fraction such as 5.0 are accepted); decimals, fractions, E notation, text and more than 200 digits are rejected with a message, and n = 0 is rejected because dividing by zero has no value. Remainder: for a ÷ n the calculator finds q and r with a = q × n + r in two ways. Floor division (the mathematical convention) takes q = ⌊a ÷ n⌋, so r has the sign of n and |r| < |n|. Truncated division takes q rounded toward zero, so r has the sign of a, as the % operator does in JavaScript. The least non-negative residue is a mod |n|. Every pair is checked to satisfy a = q × n + r before it is shown. Congruence, powers and inverses use the modulus |n|, because a ≡ b (mod n) and a ≡ b (mod −n) mean the same. Congruence is tested by whether n divides a − b. Powers use left-to-right square-and-multiply: start from a mod n and, for each following bit of the exponent, square mod n and multiply by a mod n when the bit is 1, so only numbers below n² ever appear; a negative exponent uses the inverse of a. Inverses use the extended Euclidean algorithm on n and a mod n, with rows r = s × a + t × n. When the last non-zero remainder is 1 the inverse is s reduced into 0 … n − 1, and the calculator checks a × inverse ≡ 1; otherwise it reports gcd(a, n) and the Bézout identity for that gcd. Everything is exact integer arithmetic (BigInt) and was compared with Python’s divmod, pow(a, b, n) and pow(a, −1, n) on random inputs of up to 200 digits. Long numbers in the working are shortened to their first 12 and last 8 digits, and the result rows show every digit. Everything runs in your browser.
Sources
More free tools
- Long Division CalculatorLong division with remainder and the decimal worked out step by step, the repeating block marked (1/7 = 0.(142857)). Exact for decimals and big numbers.
- Prime Number CheckerTest whether a number up to 3.3 × 10^24 is prime, find the next and previous prime, list primes in a range, count primes up to N, and see twin primes.
- GCF and LCM CalculatorFind the GCF (GCD) and LCM of 2 to 20 numbers with Euclid’s algorithm, prime factors and multiples shown, plus Bézout coefficients and fraction reduction.
- Prime Factorization CalculatorCheck if a number is prime and get its prime factors, factor tree, divisors, divisor count and sum, Euler’s totient, and the next and previous prime.
- Complex Number CalculatorAdd, subtract, multiply and divide complex numbers exactly, then find the modulus, argument, polar form, powers, square roots and roots of unity.
- System of Equations CalculatorSolve 2 or 3 linear equations exactly: row-reduction steps, determinant, Cramer’s rule and a graph. Finds one, no or infinitely many solutions.
More: Algebra and number theoryAll math & numbersAll toolsHome & DIY calculators