Skip to main content
ponderloop

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

What to calculate

Whole numbers, positive or negative, up to 200 digits each. You get both sign conventions side by side.

−17 mod 5 = 3 (mathematical) or −2 (truncated)

Mathematical: −17 = (−4) × 5 + 3. Truncated: −17 = (−3) × 5 + (−2).

MeasureMathematical (floor)Truncated (like JS %)
Quotient roundsdown (floor)toward zero
Quotient q−4−3
Remainder r3−2
Sign of rsame 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

  1. −17 ÷ 5 is not a whole number: it lies between −4 and −3.
  2. 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|.
  3. 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).
  4. 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.
  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

Row a, column n: a mod n for every a from 0 to 20 and every n from 2 to 12, computed by the calculator. For non-negative a both conventions give the same remainder.
amod 2mod 3mod 4mod 5mod 6mod 7mod 8mod 9mod 10mod 11mod 12
000000000000
111111111111
202222222222
310333333333
401044444444
512105555555
600210666666
711321077777
802032108888
910143210999
100120432101010
11123154321011
1200020543210
1311131654321
1402242065432
1510303176543
1601014207654
1712125318765
1800230420876
1911341531987
2002002642098

Eight worked examples

Each problem is the calculator’s own answer, with the working it shows.
ProblemWorkingAnswer
17 mod 517 = 3 × 5 + 22
−17 mod 5Floor: −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 multiplications9
2^1000 mod 1310 bits: 9 squarings and 5 multiplications3
Inverse of 3 mod 111 = 4 × 3 + (−1) × 114
Inverse of 6 mod 153 = (−2) × 6 + 1 × 15, so gcd(6, 15) = 3, not 1No inverse

Negative numbers: mathematical and truncated remainders

The same a ÷ n in both conventions: floor division rounds the quotient down and the remainder takes the sign of n; truncated division rounds toward zero and the remainder takes the sign of a. The last column is the least non-negative residue.
anFloor qFloor rTruncated qTruncated rLeast non-negative residue
17532322
−175−43−3−23
17−5−4−3−322
−17−53−23−23
−112−1110−111
−1007−155−14−25
−155−30−300
0500000

Days of the week as numbers mod 7, starting on a Wednesday

Count Sunday as 0 through Saturday as 6. Wednesday is 3; the day after d more days is (3 + d) mod 7, and a negative d counts backwards.
Days from todayCalculationRemainder mod 7Day of the week
1 later3 + 1 = 4; 4 mod 74Thursday
2 later3 + 2 = 5; 5 mod 75Friday
7 later3 + 7 = 10; 10 mod 73Wednesday
10 later3 + 10 = 13; 13 mod 76Saturday
30 later3 + 30 = 33; 33 mod 75Friday
100 later3 + 100 = 103; 103 mod 75Friday
365 later3 + 365 = 368; 368 mod 74Thursday
1000 later3 + 1000 = 1003; 1003 mod 72Tuesday
1 ago3 − 1 = 2; 2 mod 72Tuesday
10 ago3 − 10 = −7; −7 mod 70Sunday
100 ago3 − 100 = −97; −97 mod 71Monday

Clock arithmetic on a 12-hour clock

The hour is (start + hours later) mod 12, with 0 written as 12. Adding 12 hours, or any multiple of 12, changes nothing, which is why the clock is arithmetic mod 12.
Start (o’clock)Hours laterSumSum mod 12The clock shows
951422
9312012
1121311
1271977
3151866
6243066
1010011022
9−12−399

Modular inverses mod 12 and mod 7

a has an inverse mod n exactly when gcd(a, n) = 1. Mod 7, a prime, every a that is not a multiple of 7 has one; mod 12 only some do.
agcd(a, 12)Inverse mod 12gcd(a, 7)Inverse mod 7
11111
22none14
33none15
44none12
51513
66none16
7177none
84none11
93none14
102none15
1111112

Last digits of powers (a^k mod 10)

The last digit of a^k is a^k mod 10. Each column is computed by square-and-multiply; the digits repeat, which is why a huge exponent can be reduced.
aa¹a²a³a⁴Last digit repeatsLast digit of a¹⁰⁰
00000every power (it never changes)0
11111every power (it never changes)1
22486every 4 powers6
33971every 4 powers1
44646every 2 powers6
55555every power (it never changes)5
66666every power (it never changes)6
77931every 4 powers1
88426every 4 powers6
99191every 2 powers1

How to calculate a mod n

  1. 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.
  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.
  3. 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.
  4. 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.
  5. 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: Algebra and number theoryAll math & numbersAll toolsHome & DIY calculators