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 min18 problems
Practice Problems

Definition

Modular arithmetic is arithmetic with remainders. You fix a whole number n≥2n \geq 2, the modulus, and instead of a number you only keep its remainder after dividing by nn:
a=q×n+r,a mod n=r,0≤r≤n−1a = q \times n + r, \qquad a \bmod n = r, \qquad 0 \leq r \leq n - 1
For example, 17 mod 5=217 \bmod 5 = 2 because 17=3×5+217 = 3 \times 5 + 2.
Two numbers are congruent modulo n when they leave the same remainder. This is the same as saying that nn divides their difference:
a≡b(modn)  ⟺  n divides a−ba \equiv b \pmod{n} \iff n \text{ divides } a - b
So 38≡14(mod12)38 \equiv 14 \pmod{12}, because 38−14=24=2×1238 - 14 = 24 = 2 \times 12 (both leave remainder 22).
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≡3(mod12)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 mod 523 \bmod 5?

Worked Examples

Find 47 mod 647 \bmod 6.
1

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

6×7=426 \times 7 = 42, while 6×8=486 \times 8 = 48 is already too big → 4242
2

Write 47 as quotient times 6 plus remainder

47=7×6+547 = 7 \times 6 + 5 → remainder 55
3

Check that the remainder is between 0 and 5

0≤5≤50 \leq 5 \leq 5, so it is a valid remainder → 47 mod 6=547 \bmod 6 = 5

Common Mistakes

Writing −3 mod 12=−3-3 \bmod 12 = -3 (or 33)

Why it's wrong: A remainder must be one of 0,1,…,n−10, 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-3 + 12 = 9, so −3 mod 12=9-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=139 + 4 = 13 is right, but the last reduction is missing. Every result has to be reduced again.

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

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

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

Correct: 47 mod 6=547 \bmod 6 = 5, because 47=7×6+547 = 7 \times 6 + 5.

Reducing the exponent by the modulus: 29 mod 72^9 \bmod 7 becomes 22=42^2 = 4 because 9 mod 7=29 \bmod 7 = 2

Why it's wrong: You may reduce the base modulo nn, 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,…2, 4, 1, 2, 4, 1, \ldots (cycle length 3). 9 mod 3=09 \bmod 3 = 0, so 29≡1(mod7)2^9 \equiv 1 \pmod{7}. Check: 512=73×7+1512 = 73 \times 7 + 1.

Interactive Visual

9 o'clock plus 100 hours: watch the laps

12 spots on the dial: mod 12

121234567891011
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

0Mon1Tue2Wed3Thu4Fri5Sat6Sun

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

01234567891011
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

0123456789
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 mod 523 \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 31003^{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 nn.
    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 365365 days and 365=52×7+1365 = 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= 0, Tuesday =1= 1, and so on up to Sunday =6= 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 978030640615978030640615 the weighted sum (weights 1,3,1,3,…1, 3, 1, 3, \ldots) is 9393, and 93 mod 10=393 \bmod 10 = 3. The check digit is 10−3=710 - 3 = 7, so the full code is 97803064061579780306406157.

    2Try It Yourself

    A shop creates a product code with the 12 digits 400123456789400123456789. 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=3122 + 9 = 31 and 31 mod 24=731 \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

    • 1a mod na \bmod n is the remainder of a÷na \div n and is always one of 0,1,…,n−10, 1, \ldots, n - 1
    • 2a≡b(modn)a \equiv b \pmod{n} means that aa and bb leave the same remainder, which is the same as nn dividing a−ba - 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 nn until it lands in 0,…,n−10, \ldots, n - 1: −3 mod 12=9-3 \bmod 12 = 9
    • 6Powers repeat in cycles modulo nn: find the cycle length and reduce the exponent modulo that length, not modulo nn

    Frequently Asked Questions

    For positive numbers, yes. For negative numbers many programming languages give a negative result, for example −3-3 for −3-3 divided by 1212. In mathematics the remainder is always between 00 and n−1n - 1, so −3 mod 12=9-3 \bmod 12 = 9. The calculator on this page works that way: mod(-3, 12) gives 9.
    For positive numbers, yes. For negative numbers many programming languages give a negative result, for example −3-3 for −3-3 divided by 1212. In mathematics the remainder is always between 00 and n−1n - 1, so −3 mod 12=9-3 \bmod 12 = 9. The calculator on this page works that way: mod(-3, 12) gives 9.
    It is read as "is congruent to". 17≡5(mod12)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.
    Write a=pn+ra = pn + r and b=qn+sb = qn + s. Then a+b=(p+q)n+(r+s)a + b = (p + q)n + (r + s) and a×b=(pqn+ps+qr)n+rsa \times b = (pqn + ps + qr)n + rs. The parts with nn are multiples of nn and leave no remainder, so only r+sr + s and r×sr \times s decide the result.
    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.

    Glossary

    Modulus
    The fixed number nn you divide by; the remainders are 0,1,…,n−10, 1, \ldots, n - 1 (12 on a clock, 7 for weekdays)
    Remainder
    What is left over after dividing: in a=q×n+ra = q \times n + r with 0≤r≤n−10 \leq r \leq n - 1 it is rr
    a mod n
    The remainder of aa divided by nn, for example 17 mod 5=217 \bmod 5 = 2 and −3 mod 12=9-3 \bmod 12 = 9
    Congruent modulo n
    Two numbers with the same remainder modulo nn, written a≡b(modn)a \equiv b \pmod{n}; equivalently nn divides a−ba - 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×n+r,0≤r≤n−1a = q \times n + r, \quad 0 \leq r \leq n - 1

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

    Congruence

    a≡b(modn)  ⟺  n∣(a−b)a \equiv b \pmod{n} \iff n \mid (a - b)

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

    Reduce first

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

    The same works for subtraction and multiplication

    Negative numbers

    x mod n=(x+k×n) mod nx \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

    More in This Topic

    Even and Odd Numbers

    Elementary15 min

    Perfect Squares and Square Numbers

    Intermediate25 min