Discrete Math · Undergraduate

Modular Arithmetic and Congruences

Quick answer

Two integers are congruent modulo n, written a ≡ b (mod n), when they leave the same remainder on division by n, or equivalently when n divides a − b. Congruences can be added and multiplied like equations, so large numbers can be reduced to small remainders before any arithmetic is done. That makes questions about huge powers, last digits and days of the week quick to answer. Division works when the divisor has an inverse mod n, which happens exactly when it shares no factor with n.

What you'll learn

  • Compute remainders and write congruences
  • Reduce sums, products and powers modulo n
  • Find last digits and future days of the week
  • Find a modular inverse and solve ax ≡ b (mod n)

Clock arithmetic

Ten hours after 99 o’clock it is 77 o’clock, not 1919. A clock keeps only the remainder after dividing by 1212. Modular arithmetic does the same with any number nn, the modulus.

We say aa is congruent to bb modulo nn,

a≡b(modn)a \equiv b \pmod{n}

when aa and bb leave the same remainder on division by nn, or equivalently when nn divides a−ba - b. For example 17≡2(mod5)17 \equiv 2 \pmod 5, since 17−2=1517 - 2 = 15 is a multiple of 55.

Why you can reduce first

If a≡a′a \equiv a' and b≡b′(modn)b \equiv b' \pmod n, write a=a′+jna = a' + jn and b=b′+knb = b' + kn. Then

ab=a′b′+n(a′k+b′j+jkn)≡a′b′(modn)ab = a'b' + n(a'k + b'j + jkn) \equiv a'b' \pmod n

and sums work the same way. The extra multiples of nn never affect the remainder, so any number may be replaced by its remainder at any point in a calculation. That is what makes huge computations small: you never have to handle a number bigger than n2n^2.

Worked examples

An inverse of aa mod nn exists exactly when aa and nn share no factor greater than 11. The number 22 has no inverse mod 66: 2x2x is always even, and no even number is ≡1(mod6)\equiv 1 \pmod 6.

Common mistakes

Practice problems

  1. Find 47 mod 647 \bmod 6.

    Answer

    55

    Full solution

    47=6×7+547 = 6 \times 7 + 5.

  2. Find −13 mod 5-13 \bmod 5.

    Answer

    22

    Full solution

    −13=5×(−3)+2-13 = 5 \times (-3) + 2.

  3. Find 220 mod 52^{20} \bmod 5.

    Answer

    11

    Full solution

    24=16≡1(mod5)2^4 = 16 \equiv 1 \pmod 5, and 20=4×520 = 4 \times 5.

  4. Find 3100 mod 43^{100} \bmod 4.

    Answer

    11

    Full solution

    3≡−1(mod4)3 \equiv -1 \pmod 4, and (−1)100=1(-1)^{100} = 1.

  5. Find the inverse of 44 modulo 99.

    Answer

    77

    Full solution

    4×7=28=27+14 \times 7 = 28 = 27 + 1.

  6. Solve 5x≡3(mod7)5x \equiv 3 \pmod 7.

    Answer

    x≡2x \equiv 2

    Full solution

    The inverse of 55 is 33, since 15≡115 \equiv 1. So x≡3×3=9≡2x \equiv 3 \times 3 = 9 \equiv 2. Check: 10≡310 \equiv 3.

  7. Today is Friday. What day is it 1,0001{,}000 days from now?

    Answer

    Thursday

    Full solution

    1,000=7×142+61{,}000 = 7 \times 142 + 6, so it is 66 days after Friday.

  8. A student computes 2100 mod 72^{100} \bmod 7 as 2100 mod 7=22=42^{100 \bmod 7} = 2^2 = 4. What went wrong?

    Answer

    Exponents cannot be reduced mod 77; the answer is 22.

    Full solution

    Powers of 22 repeat with period 33 mod 77, not period 77, so the exponent reduces mod 33: 100≡1100 \equiv 1, giving 21=22^1 = 2.

Frequently asked questions

What does a ≡ b (mod n) mean?

That a and b leave the same remainder when divided by n, or equivalently that n divides a − b. For example 17 ≡ 2 (mod 5).

Can you reduce numbers before multiplying?

Yes. If a ≡ a′ and b ≡ b′ (mod n), then a + b ≡ a′ + b′ and ab ≡ a′b′ (mod n). So replace each number by its remainder first.

How do you find a large power mod n?

Reduce as you go, and look for a power that is ≡ 1. Since 2³ = 8 ≡ 1 (mod 7), 2¹⁰⁰ = 2⁹⁹ · 2 ≡ 1 · 2 = 2 (mod 7).

What is a modular inverse?

A number x with ax ≡ 1 (mod n). It exists exactly when a and n have no common factor greater than 1. The inverse of 3 mod 7 is 5, since 15 ≡ 1.

How do you find the last digit of a power?

Work mod 10. The last digits of powers repeat in a short cycle; for 7 it is 7, 9, 3, 1, so 7^2026 ends in the same digit as 7², which is 9.

What to learn next