Modulo Operation

In one sentence: The modulo operation gives the leftover amount after you split one whole number into as many equal full groups of another number as you can.

$a \bmod n = a - n \left\lfloor \frac{a}{n} \right\rfloor$

Read it out loud: “a mod n is the remainder when a is divided by n. It equals a minus n times the floor of a over n. The floor of a number means rounding it down to the nearest whole number, toward the left on the number line. The word mod is short for modulo, and it reads as the remainder.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Remainder after division: When you divide a whole number by another, you can fill as many full groups as possible, and what is left over is the remainder. For example, 17 divided by 5 gives 3 full groups of 5 with 2 left over. Written as a sentence, $17 = 3 \times 5 + 2$ , so the remainder is 2. The remainder is never as big as the group size.
Negative numbers: A negative number is less than zero. On a number line, $-7$ is seven steps to the left of 0. Subtracting a negative number is the same as adding a positive one, so $5 - (-2) = 7$ . Negative numbers matter here because a remainder can come out differently when the number being divided is below zero.
The floor sign $\lfloor x \rfloor$: The floor of $x$ , written $\lfloor x \rfloor$ , means round down to the nearest whole number, moving left on the number line. So $\lfloor 5.71 \rfloor = 5$ , and $\lfloor -2.33 \rfloor = -3$ , because $-3$ is the whole number directly to the left of $-2.33$ . Rounding toward zero would give $-2$ instead, which is a different rule.
The word mod and $a \bmod n$: The word mod is short for modulo, and it is written $a \bmod n$ . It reads ‘a mod n’ and means the remainder when $a$ is divided by $n$ . The number $n$ is the size of each group, so $17 \bmod 5 = 2$ means that 17 split into groups of 5 leaves 2 over.

What each symbol means

Symbol	Meaning
$a \bmod n$	The modulo, the remainder after dividing $a$ by $n$ . It has no unit of its own, because it is a count of the leftover items, in the same units you are counting. For a positive $n$ , the answer is always a whole number from 0 up to $n - 1$ .
$a$	The number being divided, the total we start with, such as 40 days. It can be positive or negative. Its unit is whatever you are counting, such as days, cookies or hours, and the remainder uses the same unit.
$n$	The divisor, the size of each full group, such as 7 days in a week. It is a positive whole number. It has the same unit as $a$ , so if $a$ counts days, then $n$ also counts days, and the remainder counts days too.
$\left\lfloor x \right\rfloor$	The floor of $x$ , the largest whole number that is less than or equal to $x$ . It rounds down, toward the left on the number line: the floor of 5.71 is 5, and the floor of $-2.33$ is $-3$ . It has no unit, because the result is a whole count.

The formula piece by piece

$\frac{a}{n}$: The plain division, $\frac{40}{7} \approx 5.71$ . It tells you how many groups of size $n$ fit into $a$ , counting a partial group as a fraction. Keep this number in mind, because the next piece removes the fraction.
$\left\lfloor \frac{a}{n} \right\rfloor$: The number of full groups. Rounding the division down removes the partial group, so $\lfloor 5.71 \rfloor = 5$ full groups of 7 days. This is the whole-number part of the division, called the quotient.
$n \left\lfloor \frac{a}{n} \right\rfloor$: The total size of those full groups. Multiplying the group size by the number of full groups gives the amount of $a$ that the full groups use up. In the example, $7 \times 5 = 35$ days are used by full weeks.
$a \bmod n = a - n \left\lfloor \frac{a}{n} \right\rfloor$: The whole formula in one sentence: the remainder equals the number you started with, minus the total size of the full groups. Take the whole amount, subtract what the full groups use up, and what is left over is the remainder.
$a \equiv r \pmod{n}$: A standard textbook way to write the same idea, called congruence. It says that $a$ and $r$ leave the same remainder when divided by $n$ . Here $r$ is the remainder, so $r = a \bmod n$ , and this notation is what mathematicians use when they work with remainders.

What the formula is doing, and why

The modulo operation answers one question: after you split $a$ into as many full groups of $n$ as possible, how much is left over? Seventeen cookies packed into bags of five make 3 full bags with 2 cookies left over, so $17 \bmod 5 = 2$ . The answer is a leftover count, a whole number, and it is never as big as the group size.

Why subtract? The formula is $a \bmod n = a - n \lfloor a/n \rfloor$ . The floor $\lfloor a/n \rfloor$ counts the full groups. Multiplying that count by $n$ gives the total size of those groups, and subtracting it from $a$ leaves only the leftover. For a positive $n$ , the leftover always lies from 0 up to $n - 1$ , because one more full group would have fit otherwise.

Why round down, and why do negative numbers differ? Rounding down is the choice that makes the rule work for negative numbers too. Take $-7 \bmod 3$ . The division $\frac{-7}{3} \approx -2.33$ rounds down to $-3$ , so the answer is $-7 - 3 \cdot (-3) = 2$ . Python uses this floored rule. C, C++ and Java round toward zero instead, which gives $-1$ for the same expression, so check which rule your language uses before you rely on it.

Where it shows up. The modulo operation appears wherever a count wraps around, such as clock hours, weekdays and positions in a repeating list. It is also a key step in hashing and cryptography, where a huge number is reduced to a small range. It works on whole numbers, and its answers are whole numbers too.

An everyday picture

Think of a clock with 12 hours. If it is 10 o’clock and you wait 5 hours, the clock shows 3, not 15. The hour wraps back around after each full lap of 12, so the 15 becomes 3 after one lap is removed. The modulo is the number left after removing those full laps, so adding 5 hours to 10 o’clock gives $(10 + 5) \bmod 12 = 3$ .

Worked example: Days of the week and a negative remainder

Monday is day 0, Tuesday is day 1, and so on up to Sunday, which is day 6. We want the weekday 40 days after a Monday. That is the remainder of 40 divided by 7, since every 7 days returns us to the same weekday. We also check $-7 \bmod 3$ to see how negative numbers behave.

Divide the days by the length of a week. A week has 7 days, so we divide 40 by 7: $\frac{40}{7} \approx 5.71$ . That means 5 full weeks and a bit more. The full weeks do not change the weekday, so only the part after them matters.
Round down to count the full weeks. The floor of 5.71 is $\lfloor 40/7 \rfloor = 5$ . Rounding down keeps the count of whole weeks and throws away the partial one. We will remove these 5 full weeks from the total in the next step.
Find the leftover days. Remove the 5 full weeks from the 40 days: $40 - 7 \cdot 5 = 40 - 35 = 5$ . So $40 \bmod 7 = 5$ , which means 5 extra days after the full weeks are gone.
Count those 5 days from Monday. Day 0 is Monday, so day 1 is Tuesday, day 2 is Wednesday, day 3 is Thursday, day 4 is Friday and day 5 is Saturday. The answer is Saturday, because the weekday number is always the remainder.
Work through the negative case, $-7 \bmod 3$ . We divide $\frac{-7}{3} \approx -2.33$ . Rounding down gives $-3$ , because $-3$ is the whole number to the left of $-2.33$ on the number line. Then $-7 - 3 \cdot (-3) = -7 + 9 = 2$ . Subtracting a negative number is the same as adding it back, which is why the 9 is added.
Compare with the rule that rounds toward zero. Rounding toward zero turns $-2.33$ into $-2$ instead. Then $-7 - 3 \cdot (-2) = -7 + 6 = -1$ . The same expression gives 2 in Python and $-1$ in C, which is why you must check the rule of your language before a program depends on it.
Confirm with Python. The expression -7 % 3 in Python gives 2, which matches the floored rule. A program that prints $-1$ for the same expression is using rounding toward zero, so the two rules really do differ in practice.

Answer: 40 days after a Monday is a Saturday, since $40 \bmod 7 = 5$ . With the floored rule, $-7 \bmod 3 = 2$ , which lies between 0 and $n - 1 = 2$ , as the rule promises.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Expecting a negative answer for negative numbers in every language. Python gives $-7 \bmod 3 = 2$ , but C and Java give $-1$ for the same expression.
Confusing the quotient with the remainder. $\frac{40}{7} \approx 5.71$ is the quotient, the result of dividing. The modulo is what remains after the whole groups are removed, which is 5.
Using truncation for negative numbers. Rounding toward zero and rounding down agree for positive numbers, but they give different answers for negative ones.

Where you will meet it

Clocks and calendars, where hours and weekdays wrap around after each full cycle.
Hash tables, where a hash value is turned into a bucket number with $h \bmod m$ . The bucket number is the remainder after dividing by the number of buckets.
Checking whether a whole number is even: $a \bmod 2 = 0$ means $a$ is even, because an even number leaves no remainder when divided by 2.
Cryptography such as RSA, where arithmetic is done modulo a large number $n$ , so the numbers stay small after every step.

Questions people ask

What is the difference between mod and remainder?

For positive numbers they match. For negative numbers the floored modulo always lands between 0 and $n - 1$ , while a truncated remainder can be negative, as in C and Java.

What is $a \bmod n$ when $a$ is a multiple of $n$?

It is 0. Then $\frac{a}{n}$ is a whole number, and subtracting $n$ times that number leaves nothing. For example, $35 \bmod 7 = 0$ , because 35 is exactly 5 full groups of 7.

Why does the formula need a floor?

The floor rounds the quotient down, and that choice decides what happens with negative numbers. The floor of $-2.33$ is $-3$ , which makes the remainder come out as 2.

Euclidean Algorithm: The Euclidean algorithm finds the largest number that divides two numbers evenly, by replacing the pair with a smaller pair again and again until the remainder is zero.
Hash Table Load Factor: The load factor is how full a hash table is on average: the number of keys divided by the number of buckets.
RSA Encryption: RSA lets anyone lock a message with a public key while only the owner can unlock it with a private key, because undoing a product of two secret primes is very hard.