What does the symbol $\equiv$ mean?

It is read as "is congruent to". $17 \equiv 5 \pmod{12}$ says that 17 and 5 leave the same remainder when you divide by 12 (both leave 5). It is weaker than $=$: congruent numbers can be different numbers that land on the same spot of the dial.

Why may I reduce the numbers first?

Write $a = pn + r$ and $b = qn + s$. Then $a + b = (p + q)n + (r + s)$ and $a \times b = (pqn + ps + qr)n + rs$. The parts with $n$ are multiples of $n$ and leave no remainder, so only $r + s$ and $r \times s$ decide the result.

Where is modular arithmetic used outside of school?

In check digits (barcodes, ISBN, the IBAN of a bank account, which is checked modulo 97), in computer science (hash tables, random number generators) and in cryptography: the RSA method that protects online banking computes with huge numbers modulo a product of two primes.

Teacher Resources

Modular Arithmetic

Learn clock arithmetic: remainders, a mod n, congruence modulo n, and how to use them for calendars, check digits and the last digit of huge powers.

Advanced25 minLesson

Share to Classroom

Printable worksheet

Definition

Modular arithmetic is arithmetic with remainders. You fix a whole number

n \geq 2

, the modulus, and instead of a number you only keep its remainder after dividing by

n

a = q \times n + r, \qquad a \bmod n = r, \qquad 0 \leq r \leq n - 1

For example,

17 \bmod 5 = 2

because

17 = 3 \times 5 + 2

Two numbers are congruent modulo n when they leave the same remainder. This is the same as saying that

n

divides their difference:

a \equiv b \pmod{n} \iff n \text{ divides } a - b

38 \equiv 14 \pmod{12}

, because

38 - 14 = 24 = 2 \times 12

(both leave remainder

2

A clock works exactly like this: after 12 hours the hand is back where it started, so 15 o'clock and 3 o'clock are the same spot,

15 \equiv 3 \pmod{12}

. In sums, differences and products you may replace every number by its remainder first and reduce the result once more at the end.

Try it now

What is

23 \bmod 5

Worked Examples

Find

47 \bmod 6

Find the largest multiple of 6 that is not more than 47

6 \times 7 = 42

, while

6 \times 8 = 48

is already too big →

42

Write 47 as quotient times 6 plus remainder

47 = 7 \times 6 + 5

→ remainder

5

Check that the remainder is between 0 and 5

0 \leq 5 \leq 5

, so it is a valid remainder →

47 \bmod 6 = 5

Answer: $47 \bmod 6 = 5$ , so $47 \equiv 5 \pmod{6}$ . The quotient $7$ is not part of the answer.

Common Mistakes

Writing $-3 \bmod 12 = -3$ (or $3$ )

Why it's wrong: A remainder must be one of $0, 1, \ldots, n - 1$ . Going 3 hours back from 12 o'clock does not land on a negative number, and not on 3 either.

Correct: Add the modulus until the number is in range: $-3 + 12 = 9$ , so $-3 \bmod 12 = 9$ .

Saying that 9 o'clock plus 4 hours is 13 o'clock on a 12-hour clock

Why it's wrong: The sum $9 + 4 = 13$ is right, but the last reduction is missing. Every result has to be reduced again.

Correct: $13 \bmod 12 = 1$ : the clock shows 1.

Giving the quotient instead of the remainder: $47 \bmod 6 = 7$

Why it's wrong: $47 \div 6 = 7$ remainder $5$ . The mod operation keeps only what is left over, not how many times 6 fits into 47.

Correct: $47 \bmod 6 = 5$ , because $47 = 7 \times 6 + 5$ .

Reducing the exponent by the modulus: $2^9 \bmod 7$ becomes $2^2 = 4$ because $9 \bmod 7 = 2$

Why it's wrong: You may reduce the base modulo $n$ , but not the exponent. The exponent follows the length of the power cycle, which here is 3, not 7.

Correct: Powers of 2 modulo 7 are $2, 4, 1, 2, 4, 1, \ldots$ (cycle length 3). $9 \bmod 3 = 0$ , so $2^9 \equiv 1 \pmod{7}$ . Check: $512 = 73 \times 7 + 1$ .

Interactive Visual

9 o'clock plus 100 hours: watch the laps

12 spots on the dial: mod 12

Start

Add

Start at 9 and move 100 hours forward.

Days of the week are modulo 7: guess first, then watch

7 spots on the dial: mod 7

Where will the hand land? Tap the spot on the dial.

2 + 100 ≡ ? (mod 7)

Start at Wed and move 100 days forward.

Congruent modulo 12: same spot on the dial

12 spots on the dial: mod 12

First number

Second number

38 = 3 × 12 + 2

14 = 1 × 12 + 2

38 − 14 = 24 = 2 × 12

38 ≡ 14 (mod 12)

38 and 14 land on the same spot because their difference 24 is a multiple of 12.

Numbers on the spot 2: … -10, 2, 14, 26, 38 …

Last digits of powers of 3 (modulo 10) repeat

10 spots on the dial: mod 10

Base

Exponent

Multiply by 3 again and again, and keep only the remainder each time.

Interactive Sandbox

Expression Calculator

Try these:

History

No calculations yet

Practice Problems

18 problems

Problem 1 of 18

Easy

What is

23 \bmod 5

Why It Matters

Modular arithmetic is the math of everything that goes in circles:

Time: clocks count modulo 12 or 24, weekdays modulo 7. What time is it 100 hours from now? Which day is it in 100 days?
Check digits: the last digit of a barcode (EAN-13) is chosen modulo 10, an ISBN-10 modulo 11, and the IBAN of a bank account is checked modulo 97. One mistyped digit and the check fails.
Huge numbers: you can find the last digit of $3^{100}$ (a number with 48 digits) in your head, because last digits are remainders modulo 10 and they repeat in a cycle.
Computer science: hash tables, random number generators and the RSA encryption behind online banking all calculate modulo $n$ .

You already know one case: even and odd is simply arithmetic modulo 2 (remainder 0 or 1).

Real World Applications

Calendars: Which Day Will It Be?

A week has 7 days, so the days of the week repeat modulo 7. Calendar apps, timetables and birthday puzzles use this all the time.

Example:

A normal year has $365$ days and $365 = 52 \times 7 + 1$ . So a birthday on a Monday this year falls on a Tuesday next year (unless 29 February comes in between).

1Try It Yourself

Today is Wednesday. Your exchange trip starts in exactly 100 days. Number the days Monday $= 0$ , Tuesday $= 1$ , and so on up to Sunday $= 6$ .

On which day of the week does the trip start?

Step 1: Choose the right answer

Pick the day:

Barcodes and Check Digits

The last digit of every EAN-13 barcode is a check digit, chosen with arithmetic modulo 10. The scanner computes it again and rejects a code with a misread digit.

Example:

For the book code $978030640615$ the weighted sum (weights $1, 3, 1, 3, \ldots$ ) is $93$ , and $93 \bmod 10 = 3$ . The check digit is $10 - 3 = 7$ , so the full code is $9780306406157$ .

2Try It Yourself

A shop creates a product code with the 12 digits $400123456789$ . The digits in positions 1, 3, 5, ... count once, the digits in positions 2, 4, 6, ... count three times. The check digit makes the total a multiple of 10.

What is the check digit?

Step 1: Write the mathematical expression

Check digit:

Shift Work and the 24-Hour Clock

Train timetables, hospital shifts and flight plans use the 24-hour clock, which is arithmetic modulo 24.

Example:

A night shift starts at 22:00 and lasts 9 hours: $22 + 9 = 31$ and $31 \bmod 24 = 7$ , so it ends at 07:00.

3Try It Yourself

A machine test in a factory starts at 19:00 and runs for 75 hours without a break.

At what hour (0 to 23) does the test end?

Step 1: Write the mathematical expression

End hour:

Key Takeaways

1 $a \bmod n$ is the remainder of $a \div n$ and is always one of $0, 1, \ldots, n - 1$
2 $a \equiv b \pmod{n}$ means that $a$ and $b$ leave the same remainder, which is the same as $n$ dividing $a - b$
3A clock is arithmetic modulo 12, the 24-hour clock modulo 24, the days of the week modulo 7 and even/odd modulo 2
4In sums, differences and products you may reduce every number first, then reduce the result once more
5For a negative number add $n$ until it lands in $0, \ldots, n - 1$ : $-3 \bmod 12 = 9$
6Powers repeat in cycles modulo $n$ : find the cycle length and reduce the exponent modulo that length, not modulo $n$

Frequently Asked Questions

For positive numbers, yes. For negative numbers many programming languages give a negative result, for example

-3

for

-3

divided by

12

. In mathematics the remainder is always between

0

and

n - 1

, so

-3 \bmod 12 = 9

. The calculator on this page works that way: mod(-3, 12) gives 9.

Glossary

Modulus: The fixed number $n$ you divide by; the remainders are $0, 1, \ldots, n - 1$ (12 on a clock, 7 for weekdays)
Remainder: What is left over after dividing: in $a = q \times n + r$ with $0 \leq r \leq n - 1$ it is $r$
a mod n: The remainder of $a$ divided by $n$ , for example $17 \bmod 5 = 2$ and $-3 \bmod 12 = 9$
Congruent modulo n: Two numbers with the same remainder modulo $n$ , written $a \equiv b \pmod{n}$ ; equivalently $n$ divides $a - b$
Cycle length: How many steps it takes until the remainders of powers start to repeat, for example 4 for the last digits of powers of 3
Check digit: An extra digit at the end of a code (barcode, ISBN) chosen so that a weighted sum is divisible by 10 or 11

Formula Card

Division with remainder

a = q \times n + r, \quad 0 \leq r \leq n - 1

$r$ is $a \bmod n$, $q$ is the quotient

Congruence

a \equiv b \pmod{n} \iff n \mid (a - b)

Same remainder, or: the difference is a multiple of $n$

Reduce first

(a + b) \bmod n = \big((a \bmod n) + (b \bmod n)\big) \bmod n

The same works for subtraction and multiplication

Negative numbers

x \bmod n = (x + k \times n) \bmod n

Add a multiple of $n$ until the number lands in $0, \ldots, n - 1$: $-3 + 12 = 9$

Today's challengeOne problem, three tries

Modular Arithmetic

Definition

Worked Examples

Common Mistakes

Interactive Visual

Interactive Sandbox

Expression Calculator

History

Practice Problems

Why It Matters

Real World Applications

Calendars: Which Day Will It Be?

Barcodes and Check Digits

Shift Work and the 24-Hour Clock

Key Takeaways

Frequently Asked Questions

Glossary

Formula Card

Division with remainder

Congruence

Reduce first

Negative numbers

More in This Topic

Even and Odd Numbers

Perfect Squares and Square Numbers