📋 Prerequisites

• Divisibility & Primes

Modular arithmetic is "clock math" — numbers wrap around after reaching a certain value called the modulus. It's the single most powerful tool in number theory. Once you think in terms of remainders, divisibility rules, last-digit problems, and cyclic patterns all become trivial. Master the basics here, then we'll go deep.

📚 Key Concepts

Congruence Definition

We say $a$ is congruent to $b$ modulo $m$ if $m$ divides $(a - b)$.

\[ a \equiv b \pmod{m} \quad \Longleftrightarrow \quad m \mid (a - b) \]

Intuitively: a and b leave the same remainder when divided by m.

Examples:

• $ 17 \equiv 5 \pmod{12} $ (both have remainder 5 when divided by 12)
• $ 24 \equiv 0 \pmod{6} $ (24 is divisible by 6)
• $ -1 \equiv 9 \pmod{10} $ (-1 + 10 = 9, same remainder)

Basic Arithmetic with Congruences

If $ a \equiv b \pmod{m} $ and $ c \equiv d \pmod{m} $, then:

• Addition: $ a + c \equiv b + d \pmod{m} $
• Subtraction: $ a - c \equiv b - d \pmod{m} $
• Multiplication: $ a \cdot c \equiv b \cdot d \pmod{m} $
• Scalar multiplication: $ ka \equiv kb \pmod{m} $ for any integer k

Important: Division doesn't always work! You can only divide both sides by k if gcd(k, m) = 1. We'll cover modular inverses for this.

Reducing Modulo m

Any integer can be reduced to its residue — the unique remainder r where $ 0 \leq r < m $.

To find a mod m: divide by m, take the positive remainder.

For negative numbers: add multiples of m until you get into [0, m).

Example: -3 mod 7 = -3 + 7 = 4. So $ -3 \equiv 4 \pmod{7} $.

Last Digit Problems (mod 10)

The last digit of a number is just the number mod 10.

Last digits of powers cycle! For example, powers of 2:

• \((2^{1} = 2 \\to\) last digit 2\)
• \((2^{2} = 4 \\to\) last digit 4\)
• \((2^{3} = 8 \\to\) last digit 8\)
• \((2^{4} = 16 \\to\) last digit 6\)
• \((2^{5} = 32 \\to\) last digit 2 (cycle repeats)\)

Cycle length = 4. So \(2^{n}\) last digit depends on n mod 4.

Why Divisibility Rules Work

Since $ 10 \equiv 0 \pmod{2} $ and $ 10 \equiv 0 \pmod{5} $, only the last digit matters for divisibility by 2 or 5.

Since $ 10 \equiv 1 \pmod{3} $ and $ 10 \equiv 1 \pmod{9} $, we have $ 10^k \equiv 1^k = 1 \pmod{3} $. So a number equals the sum of its digits mod 3 (and mod 9).

Since $ 10 \equiv -1 \pmod{11} $, we have $ 10^k \equiv (-1)^k \pmod{11} $. This gives the alternating-sum rule for 11.

Modular arithmetic is the proof behind every divisibility rule!

Residue Classes

Modulo m, there are exactly m distinct residue classes: {0, 1, 2, ..., m-1}.

Every integer belongs to exactly one class. Two numbers in the same class are congruent mod m.

The set $ \mathbb{Z}/m\mathbb{Z} = \{0, 1, 2, ..., m-1\} $ is the set of residues mod m.

Modular Exponentiation (Basic)

To compute $ a^n \pmod{m} $ efficiently, you can reduce at each step:

• Start with result = 1
• Multiply by a, reduce mod m
• Repeat n times (or use faster methods like fast exponentiation — covered later)

Key idea: you never need to deal with huge numbers. Reduce after every multiplication.

Solving Simple Congruences

$ ax \equiv b \pmod{m} $ has a solution iff gcd(a, m) divides b.

If gcd(a, m) = 1, there's exactly one solution mod m (found via modular inverse).

If gcd(a, m) = d > 1 and d | b, there are d solutions mod m.

If d doesn't divide b, no solution.

✏️ Example Problems