Modular arithmetic — definition, addition, multiplication, congruence

Overview

Modular arithmetic is arithmetic that "wraps around" after reaching a certain value called the modulus. It's the mathematical foundation of clock arithmetic, cyclic patterns, cryptography, and computer science hash functions.

Core Concepts

Instead of numbers extending infinitely, we partition them into equivalence classes based on their remainder when divided by a fixed number (the modulus). This lets us:

• Simplify calculations with large numbers (cryptography uses this!)
• Find patterns in divisibility
• Work with cyclic structures (days of week, months, rotations)

Key insight: Two numbers are "the same" in modular arithmetic if they leave the same remainder when divided by the modulus.

Equivalent definition: $a \equiv b \pmod{n}$ if and only if $a$ and $b$ leave the same remainder when divided by $n$.

What does this mean? The difference between $a$ and $b$ is a multiple of $n$. They're in the same "bucket" when we divide integers into groups based on remainder.

From First Principles:

1. Addition: If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then: $a + c \equiv b + d \pmod{n}$

Why?

• We know $a - b = k_1n$ and $c - d = k_2n$ for some integers $k_1, k_2$
• Add these: $(a - b) + (c - d) = k_1n + k_2n$
• Rearrange: $(a + c) - (b + d) = (k_1 + k_2)n$
• Since $k_1 + k_2$ is an integer, $(a+c) \equiv (b+d) \pmod{n}$

2. Multiplication: If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then: $ac \equiv bd \pmod{n}$

Why?

• We have $a = b + k_1n$ and $c = d + k_2n$
• Multiply: $ac = (b + k_1n)(d + k_2n)$
• Expand: $ac = bd + bk_2n + dk_1n + k_1k_2n^2$
• Factor: $ac = bd + n(bk_2 + dk_1 + k_1k_2n)$
• Therefore: $ac - bd = n \cdot (\text{integer})$, so $ac \equiv bd \pmod{n}$

3. Power Rule: If $a \equiv b \pmod{n}$, then: $a^k \equiv b^k \pmod{n}$

Why? Apply the multiplication rule repeatedly $k$ times.

Solution:

• Method 1 (Difference): $23 - 8 = 15 = 3 \times 5$. Since the difference is a multiple of 5, yes.
• Method 2 (Remainder): $23 = 4 \times 5 + 3$ (remainder 3), $8 = 1 \times 5 + 3$ (remainder 3). Same remainder, yes.

Why this matters: Both numbers are in the "remainder 3" equivalence class when working mod 5.

Solution:

• Step 1: Reduce each number first

  • $17 = 2 \times 7 + 3$, so $17 \equiv 3 \pmod{7}$
  • $23 = 3 \times 7 + 2$, so $23 \equiv 2 \pmod{7}$
  • Why this step? Smaller numbers are easier to work with, and we can reduce before operating.

• Step 2: Add the reduced numbers

  • $3 + 2 = 5$
  • Why this step? By the addition rule, $(17 + 23) \equiv (3 + 2) \pmod{7}$

• Step 3: Result

  • $5 < 7$, so $5$ is already in standard form
  • Why this step? We want the answer in the range $[0, n-1]$.

Answer: $(17 + 23) \equiv 5 \pmod{7}$

Verification: $17 + 23 = 40 = 5 \times 7 + 5$. Remainder is 5. ✓

Solution:

• Step 1: Reduce each factor

  • $13 = 2 \times 5 + 3$, so $13 \equiv 3 \pmod{5}$
  • $8 = 1 \times 5 + 3$, so $8 \equiv 3 \pmod{5}$
  • Why this step? Working with smaller numbers prevents overflow and simplifies calculation.

• Step 2: Multiply reduced numbers

  • $3 \times 3 = 9$
  • Why this step? By multiplication rule, $(13 \times 8) \equiv (3 \times 3) \pmod{5}$

• Step 3: Reduce the result

  • $9 = 1 \times 5 + 4$, so $9 \equiv 4 \pmod{5}$
  • Why this step? Final answer should be in standard form $[0, 4]$.

Answer: $(13 \times 8) \equiv 4 \pmod{5}$

Verification: $13 \times 8 = 104 = 20 \times 5 + 4$. Remainder is 4. ✓

Solution:

• Step 1: Reduce the base

  • $7 = 1 \times 6 + 1$, so $7 \equiv 1 \pmod{6}$
  • Why this step? If the base reduces to something simple, the power becomes trivial.

• Step 2: Apply power rule

  • $7^{100} \equiv 1^{100} \pmod{6}$
  • Why this step? By the power rule, congruence is preserved under exponentiation.

• Step 3: Evaluate

  • $1^{100} = 1$
  • Why this step? Any power of 1 is 1.

Answer: $7^{100} \equiv 1 \pmod{6}$

Key insight: Reducing the base first can make impossible-looking calculations trivial!

Why it feels right: This actually works! But for large numbers (like $1234567 + 9876543 \pmod{7}$), calculating the full sum first can cause overflow or unnecessary complexity.

The fix: Reduce each operand first, then operate. This is always valid by the addition/multiplication rules, and it's more efficient.

Steel-man: The "calculate then reduce" approach is mathematically correct, just computationally inefficient. The modular arithmetic rules exist precisely to let us reduce during calculation.

Why it feels right: In regular arithmetic, we can divide both sides by the same number.

The fix: Division in modular arithmetic is not always defined. You can only divide by $a$ if $\gcd(a, n) = 1$ (i.e., $a$ and $n$ are coprime). Here, $\gcd(6, 15) = 3 \neq 1$, so we can't divide by 6.

Correct approach:

• Notice $\gcd(6, 15) = 3$ divides both 6 and 9
• Simplify: $6x \equiv 9 \pmod{15}$ becomes $2x \equiv 3 \pmod{5}$
• Now we can solve: multiply both sides by the modular inverse of 2 5

Steel-man: The intuition from regular algebra is powerful, but modular arithmetic has different rules. Always check if division is valid by checking the gcd.

Why it feels right: In programming, some languages return negative remainders.

The fix: In mathematics, we always want the result in $[0, n-1]$. Convert negative numbers: $-3 \equiv -3 + 7 \equiv 4 \pmod{7}$

General rule: If you get a negative result $r$, add multiples of $n$ until you reach $[0, n-1]$: $r \equiv r + kn \pmod{n}$ where $k$ is chosen so the result is non-negative.

This is modular arithmetic! The "12" is called the modulus—it's when you wrap around. Two positions are the "same" if they're the same spot on the circle.

When we write $13 \equiv 1 \pmod{12}$, we're saying "13 and 1 are the same position on a12-hour clock."

The cool part: you can add and multiply on this circular track, and everything still works! If you're at position 5 and a friend is at position 8, together you've gone $5 + 8 = 13$ steps, which is position 1. If you go around the track 5 times, taking 8 steps each time, you go $5 \times 8 = 40$ steps total, which lands you at position 4 (because $40 = 3 \times 12 + 4$).

Reminder: $a \equiv b \pmod{n}$ means "$a$ and $b$ show the same time on an $n$-hour clock."

Properties of Congruence

Congruence modulo $n$ is an equivalence relation, meaning:

1. Reflexive: $a \equiv a \pmod{n}$ (every number is congruent to itself)
2. Symmetric: If $a \equiv b \pmod{n}$, then $b \equiv a \pmod{n}$
3. Transitive: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a \equiv c \pmod{n}$

Why this matters: These properties mean congruence partitions the integers into distinct equivalence classes (called residue classes). Every integer belongs to exactly one class.

For modulus $n$, there are exactly $n$ residue classes: $[0], [1], [2], \ldots, [n-1]$.

The Residue Classes

For modulus 5, the residue classes are:

• $[0] = \{\ldots, -10, -5, 0, 5, 10, 15, \ldots\}$
• $[1] = \{\ldots, -9, -4, 1, 6, 11, 16, \ldots\}$
• $[2] = \{\ldots, -8, -3, 2, 7, 12, 17, \ldots\}$
• $[3] = \{\ldots, -7, -2, 3, 8, 13, 18, \ldots\}$
• $[4] = \{\ldots, -6, -1, 4, 9, 14, 19, \ldots\}$

Every integer is in exactly one of these classes. We write $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$ for the set of residue classes mod 5.

Connections

• Division Algorithm — the foundation of remainders
• GCD and LCM — determines when modular division is possible
• Fermats Little Theorem — uses modular exponentiation
• Eulers Theorem — generalizes Fermat's theorem using modular arithmetic
• Chinese Remainder Theorem — solves systems of congruences
• Modular Inverses — division in modular arithmetic
• RSA Cryptography — built entirely on modular arithmetic with large primes
• Linear Congruences — solving $ax \equiv b \pmod{n}$
• Quadratic Residues — which numbers are perfect squares mod $n$

Practice Problems

1. Verify that $17 \equiv 38 \pmod{7}$ using both definitions
2. Compute $(45 + 67) \bmod 11$ by reducing first
3. Find $(13 \times 17) \bmod 6$ efficiently
4. Calculate $9^{50} \bmod 8$ (hint: reduce the base first!)
5. Prove that if $a \equiv b \pmod{n}$, then $a^2 \equiv b^2 \pmod{n}$
6. Find all $x$ such that $x^2 \equiv 1 \pmod{8}$

#flashcards/maths

What is the definition of congruence modulo n? :: Two integers $a$ and $b$ are congruent modulo $n$ (written $a \equiv b \pmod{n}$) if their difference is a multiple of $n$, i.e., $a - b = kn$ for some integer $k$.

State the addition rule in modular arithmetic :: If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a + c \equiv b + d \pmod{n}$.

Why can we reduce numbers before operating in modular arithmetic? :: Because the addition and multiplication rules guarantee that $(a \bmod n) + (b \bmod n) \equiv (a+b) \pmod{n}$, and similarly for multiplication. This makes calculations more efficient.

How do you handle negative numbers in modular arithmetic? :: Add multiples of the modulus until the result is in the range $[0, n-1]$. For example, $-3 \equiv 4 \pmod{7}$ because $-3 + 7 = 4$.

What is the clock face analogy for modular arithmetic? :: Modular arithmetic works like a clock: after reaching the modulus value, you wrap around to 0. For mod 12, after 11 comes 0 again. Two numbers are congruent if they point to the same position on the clock.

Concept Map

Hinglish (regional understanding)