Modular Arithmetic Explained: Congruences, Rules & Examples

Modular arithmetic is arithmetic where numbers wrap around after reaching a fixed value called the modulus, so only the remainder matters. Working modulo 12, the number 17 behaves exactly like 5, because both leave a remainder of 5 when divided by 12. This is written 17 ≡ 5 (mod 12).

A clock is the everyday version. Eight hours after 9 o’clock is 5 o’clock, not 17 o’clock, because the clock face resets every 12 hours. Modular arithmetic makes that resetting behaviour into a full number system with its own rules for adding, subtracting, multiplying and taking powers.

This guide builds the system from the clock upward: congruence notation, residue classes, the four operation rules with worked examples, why division mostly fails, how negative numbers behave, and where the whole thing gets used.

The Clock Picture

Start with a 12 hour clock. Counting forward from 9 o’clock by 8 hours passes 10, 11, 12, then resets and continues 1, 2, 3, 4, 5.

In ordinary arithmetic, 9 + 8 = 17. On the clock, the answer is 5. The two answers agree once you notice that 17 and 5 differ by exactly one full turn of 12:

17 = 12 × 1 + 5

The clock throws away the whole turns and keeps the remainder. That is the entire idea. The number 12 here is the modulus, and the arithmetic is said to be modulo 12.

Change the modulus and you change the clock. Modulo 7 wraps every week, modulo 60 wraps every minute of an hour, modulo 2 wraps every other number and separates even from odd.

Congruence Notation

Rather than write “17 and 5 leave the same remainder on division by 12” every time, mathematics uses a compact symbol.

a ≡ b (mod n) is read “a is congruent to b modulo n” and means that a and b leave the same remainder when divided by n.

Three examples, all true:

17 ≡ 5  (mod 12)        both leave 5
38 ≡ 2  (mod 12)        both leave 2
-7 ≡ 5  (mod 12)        both leave 5

The symbol ≡ has three bars rather than two, and that difference is deliberate. Writing 17 = 5 would be false. Writing 17 ≡ 5 (mod 12) is true, and the “(mod 12)” is part of the statement, not a footnote. Drop it and the sentence means nothing.

There is an equivalent definition that is often easier to check:

a ≡ b (mod n) exactly when n divides a − b.

Testing 38 ≡ 2 (mod 12): the difference is 36, and 12 divides 36, so the congruence holds. This version handles negative numbers without any extra thought, since −7 − 5 = −12, which 12 divides.

Residues and Residue Classes

The residue of a modulo n is the remainder it leaves, chosen from 0 to n − 1. Modulo 5, the possible residues are 0, 1, 2, 3 and 4, and every integer has exactly one of them.

Sorting all the integers by residue splits them into n groups, called residue classes or congruence classes. Modulo 5:

Every integer sits in exactly one row, and no integer sits in two. That is what makes modular arithmetic well behaved: instead of infinitely many numbers, there are only five things to work with modulo 5.

The set of these classes is written Z/nZ or Z_n. Modulo 5 it has five elements, which is why modular arithmetic is sometimes described as arithmetic on a finite set.

Rule 1: Addition

If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n).

In plain terms: you may replace any number by its remainder before adding, and the answer is unchanged.

Example. Find (23 + 41) mod 7.

The direct route: 23 + 41 = 64, and 64 = 7 × 9 + 1, so the answer is 1.

The modular route reduces first:

23 ≡ 2 (mod 7)        since 23 = 7 × 3 + 2
41 ≡ 6 (mod 7)        since 41 = 7 × 5 + 6

2 + 6 = 8 ≡ 1 (mod 7)

Both give 1. The second route never handled a number larger than 8, which is the practical point: reducing early keeps the arithmetic small.

Rule 2: Subtraction

If a ≡ b (mod n) and c ≡ d (mod n), then a − c ≡ b − d (mod n).

Example. Find (15 − 28) mod 9.

15 ≡ 6 (mod 9)
28 ≡ 1 (mod 9)

6 − 1 = 5

So the answer is 5. Checking directly, 15 − 28 = −13, and −13 + 18 = 5, so −13 ≡ 5 (mod 9). ✓

Subtraction can drop below zero, and that is allowed. Add copies of the modulus until the result lands in the range 0 to n − 1.

Rule 3: Multiplication

If a ≡ b (mod n) and c ≡ d (mod n), then a × c ≡ b × d (mod n).

Example. Find (17 × 23) mod 11.

Directly, 17 × 23 = 391, and 391 = 11 × 35 + 6, so the answer is 6.

Reducing first:

17 ≡ 6 (mod 11)
23 ≡ 1 (mod 11)

6 × 1 = 6

Same answer, and the largest number involved was 6 instead of 391. On big problems this saving is the difference between possible and impossible by hand.

Rule 4: Powers

Repeated multiplication inherits the multiplication rule, so:

If a ≡ b (mod n), then a^k ≡ b^k (mod n) for any positive whole number k.

Example. Find 3⁴ mod 7.

3² = 9 ≡ 2 (mod 7)
3⁴ = (3²)² ≡ 2² = 4 (mod 7)

So 3⁴ ≡ 4 (mod 7). Checking, 81 = 7 × 11 + 4. ✓

Powers modulo n eventually repeat, and spotting the cycle is often the fastest route to a huge exponent.

Example. Find 7¹⁰⁰ mod 10.

7¹ ≡ 7      7² ≡ 9      7³ ≡ 3      7⁴ ≡ 1
7⁵ ≡ 7      7⁶ ≡ 9      7⁷ ≡ 3      7⁸ ≡ 1

The pattern repeats every 4 steps. Since 100 is a multiple of 4, 7¹⁰⁰ lands where 7⁴ does:

7¹⁰⁰ ≡ 1 (mod 10)

Cycle spotting works well for small moduli. For a large exponent and a large modulus, the systematic method is repeated squaring, covered in modular exponentiation.

Why Division Is Different

The first three rules look like ordinary arithmetic, so it is natural to expect division to work too. It does not.

Cancellation fails. Modulo 10:

2 × 3 = 6
2 × 8 = 16 ≡ 6 (mod 10)

so   2 × 3 ≡ 2 × 8  (mod 10)

Cancelling the 2 from both sides would give 3 ≡ 8 (mod 10), which is false. The numbers 3 and 8 leave different remainders on division by 10.

The reason is that 2 and 10 share the factor 2. Division only works when you can find a number that undoes the multiplication.

Multiplicative inverses. A number x is the inverse of a modulo n when

a · x ≡ 1 (mod n)

Modulo 10, the inverse of 3 is 7, because 3 × 7 = 21 ≡ 1 (mod 10). So “dividing by 3” modulo 10 means multiplying by 7.

The number 2 has no inverse modulo 10. No multiple of 2 ever ends in 1, so no x satisfies 2x ≡ 1 (mod 10). The condition is exact:

a has an inverse modulo n if and only if gcd(a, n) = 1.

Finding these inverses, and the methods that produce them, are covered in modular inverse.

Negative Numbers Modulo n

Negative numbers are fully allowed, and they reduce the same way: add multiples of n until the result is between 0 and n − 1.

-17 (mod 5):    -17 + 20 = 3        so  -17 ≡ 3 (mod 5)
-7  (mod 12):   -7 + 12 = 5         so  -7  ≡ 5 (mod 12)

In mathematics, the residue is conventionally taken as the non-negative one, so −17 mod 5 is reported as 3. Programming languages do not all agree with that. Python returns 3, while C, Java and JavaScript return −2 for the same calculation, because they define the operation by truncating the quotient rather than flooring it. Neither is wrong; they answer slightly different questions. The remainder of negative numbers guide sets the two conventions side by side.

A useful trick falls out of this. Modulo 3, the number 2 is congruent to −1, and small negative representatives often simplify a calculation:

2¹⁰⁰ ≡ (-1)¹⁰⁰ = 1  (mod 3)

Modular Arithmetic and the % Operator

The % operator found in most programming languages computes a remainder, so it is the closest available tool for modular arithmetic, but the two are not identical.

To get the mathematical residue reliably in a truncating language, force the sign:

((a % n) + n) % n

The language-by-language behaviour is compared in modulo in Python, JavaScript and C, and the Modulo Calculator reports a mod n under each convention.

Where Modular Arithmetic Is Used

• Calendars. Days of the week repeat with period 7. If today is Sunday, then 1,000 days from now is 1,000 mod 7 = 6 days past Sunday, which is Saturday.
• Check digits. ISBN-10, IBAN and many barcode standards compute a final digit as a weighted sum reduced modulo 11 or 97, so a single mistyped digit fails the check.
• Cryptography. RSA encrypts by raising a message to a power modulo a large number. Its security rests on the difficulty of undoing that step.
• Hashing. Mapping a key into a table of fixed size is hash mod table_size, which is why table sizes are often chosen to be prime.
• Pseudorandom numbers. Linear congruential generators produce each value as (a·x + c) mod m.
• Divisibility tests. The rule for 9 works because 10 ≡ 1 (mod 9), so a number is congruent to its digit sum. That is the basis of the divisibility rules.

Systems of Congruences

A single congruence such as x ≡ 3 (mod 7) has infinitely many solutions: 3, 10, 17, 24 and so on. Ask for a number satisfying several congruences at once and the problem becomes more interesting:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

When the moduli have no factors in common, a solution always exists and is unique modulo the product of the moduli. Here the product is 105, and the solution is x ≡ 23 (mod 105).

The method that produces that answer is the Chinese Remainder Theorem, and the Chinese Remainder Theorem Calculator solves any such system step by step.

Practice Examples

1. Reduce 47 modulo 9.
2. Reduce −25 modulo 7.
3. Compute (38 + 57) mod 11 by reducing first.
4. Compute (64 − 91) mod 5.
5. Compute (19 × 24) mod 7 by reducing first.
6. Compute 5⁶ mod 13.
7. Find the residue of 2⁴⁰ modulo 5 by spotting the cycle.
8. Find the inverse of 5 modulo 13 by testing values.
9. Explain why 4 has no inverse modulo 12.
10. Today is Sunday. What day is it in 1,000 days?

Answers

1. 47 = 9 × 5 + 2, so 47 ≡ 2 (mod 9).
2. −25 + 28 = 3, so −25 ≡ 3 (mod 7).
3. 38 ≡ 5 and 57 ≡ 2, so the sum is 5 + 2 = 7 (mod 11). Check: 95 = 11 × 8 + 7. ✓
4. 64 ≡ 4 and 91 ≡ 1, so 4 − 1 = 3 (mod 5). Check: −27 + 30 = 3. ✓
5. 19 ≡ 5 and 24 ≡ 3, so 5 × 3 = 15 ≡ 1 (mod 7). Check: 456 = 7 × 65 + 1. ✓
6. 5² = 25 ≡ 12 ≡ −1 (mod 13), so 5⁶ = (5²)³ ≡ (−1)³ = −1 ≡ 12 (mod 13).
7. The powers of 2 modulo 5 run 2, 4, 3, 1 and then repeat with period 4. Since 40 is a multiple of 4, 2⁴⁰ ≡ 1 (mod 5).
8. Testing multiples of 5: 5 × 8 = 40 = 13 × 3 + 1, so the inverse is 8.
9. gcd(4, 12) = 4, which is not 1. Every multiple of 4 is even and 12 is even, so 4x is always even modulo 12 and can never equal the odd value 1.
10. 1,000 = 7 × 142 + 6, so the day advances 6 places from Sunday, landing on Saturday.

Modular Arithmetic FAQ

What does a ≡ b (mod n) mean?

It means a and b leave the same remainder when divided by n, equivalently that n divides a − b. So 23 ≡ 3 (mod 10) because both leave 3, and because 10 divides 20.

What is the difference between mod and modulo?

They refer to the same idea in different grammatical roles. “Modulo n” describes the setting of a whole statement, as in 17 ≡ 5 (mod 12). “17 mod 12” names the specific value 5, the residue. In code, mod or % is the operator that computes that value.

Is modular arithmetic the same as finding a remainder?

Finding a remainder is one step inside it. Modular arithmetic goes further by treating every number with the same remainder as interchangeable, which is what allows you to reduce numbers before adding or multiplying rather than after. The single-step calculation is covered in how to find the remainder.

Why can’t you divide in modular arithmetic?

Because cancelling a common factor is not always valid. Modulo 10, 2 × 3 and 2 × 8 both give 6, yet 3 and 8 are not congruent. Division works only by multiplying by a modular inverse, and an inverse of a exists only when gcd(a, n) = 1.

What is a residue class?

It is the set of all integers leaving the same remainder on division by n. Modulo 5 there are five of them, and every integer belongs to exactly one. Working with classes instead of individual numbers is what turns an infinite number system into a finite one.

Can the modulus be negative or zero?

The modulus is normally taken as a positive integer greater than 1. A modulus of 0 makes no sense, since division by zero is undefined. A negative modulus adds nothing new, because n and −n produce identical residue classes.

How do you handle a negative number modulo n?

Add multiples of n until the value lands between 0 and n − 1. For −25 modulo 7, adding 28 gives 3. Note that a programming language may report −4 instead, since several languages let the remainder take the sign of the dividend.

What is modular arithmetic used for in real life?

Clocks and calendars, ISBN and IBAN check digits, hash tables, pseudorandom number generators, cyclic error detection, and public-key cryptography such as RSA, which is built on raising numbers to powers modulo a large integer.