Introduction to Modulo Arithmetic and Congruence

TL;DR

Modulo arithmetic is like telling time on a clock, where numbers "wrap around" after reaching a certain point. It helps us understand remainders when one number divides another. Congruence is simply a fancy way to say two numbers have the same remainder when divided by the same number.

1. The Mental Model

Imagine a clock face. When you go past 12, you don't say "13 o'clock"; you say "1 o'clock" again. Modulo arithmetic works just like this, resetting numbers after a specific value (the "modulus").

2. The Core Material

Modulo arithmetic focuses on the remainder when you divide one number by another. The "modulus" is that other number.

What is "Modulo"?

Photo by Ann H on Pexels

When you see "$a \pmod{n}$" (read as "$a$ modulo $n$"), it means "the remainder when $a$ is divided by $n$."

For example:
* $10 \pmod{3}$ is $1$, because $10 = 3 \times 3 + 1$.
* $15 \pmod{7}$ is $1$, because $15 = 2 \times 7 + 1$.
* $20 \pmod{5}$ is $0$, because $20 = 4 \times 5 + 0$.

It's essentially the % operator in many programming languages.

# Python examples
print(10 % 3) # Output: 1
print(15 % 7) # Output: 1
print(20 % 5) # Output: 0
print(7 % 10) # Output: 7 (7 divided by 10 is 0 with a remainder of 7)

What is "Congruence"?

Photo by Ann H on Pexels

Two numbers, $a$ and $b$, are congruent modulo $n$ if they have the same remainder when divided by $n$. We write this as $a \equiv b \pmod{n}$. This means that $a - b$ is a multiple of $n$.

For example:
* $10 \equiv 1 \pmod{3}$ because $10 \div 3$ has remainder $1$, and $1 \div 3$ has remainder $1$. Also, $10 - 1 = 9$, which is a multiple of $3$.
* $15 \equiv 8 \pmod{7}$ because $15 \div 7$ has remainder $1$, and $8 \div 7$ has remainder $1$. Also, $15 - 8 = 7$, which is a multiple of $7$.
* $20 \equiv 0 \pmod{5}$ because $20 \div 5$ has remainder $0$, and $0 \div 5$ has remainder $0$. Also, $20 - 0 = 20$, which is a multiple of $5$.

Congruence is an equivalence relation, meaning it shares properties with equality:
* Reflexive: $a \equiv a \pmod{n}$ (any number is congruent to itself)
* Symmetric: If $a \equiv b \pmod{n}$, then $b \equiv a \pmod{n}$
* Transitive: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a \equiv c \pmod{n}$

graph TD
    A["Start with a number (e.g., 17)"] --> B{"Divide by the modulus (e.g., mod 5)"}
    B -- "Result is a quotient and remainder" --> C["Identify the remainder (e.g., 2)"]
    C --> D["This remainder is the result of '17 mod 5'"]
    C --> E{"Compare another number (e.g., 7) to the same modulus"}
    E --> F["Find its remainder (e.g., 2)"]
    F -- "Remainders are the same" --> G["Numbers are congruent modulo n (17 ≡ 7 mod 5)"]

3. Worked Example

Let's work with mod 7.

Question: Is $25 \equiv 11 \pmod{7}$?

Step 1: Find the remainder of the first number divided by the modulus.
$25 \div 7$:
$7 \times 3 = 21$
$25 - 21 = 4$
So, $25 \pmod{7} = 4$.

Step 2: Find the remainder of the second number divided by the modulus.
$11 \div 7$:
$7 \times 1 = 7$
$11 - 7 = 4$
So, $11 \pmod{7} = 4$.

Step 3: Compare the remainders.
Both $25 \pmod{7}$ and $11 \pmod{7}$ give a remainder of $4$.

Conclusion: Yes, $25 \equiv 11 \pmod{7}$ because they both have a remainder of $4$ when divided by $7$.

Alternatively, check if their difference is a multiple of the modulus:
$25 - 11 = 14$.
Is $14$ a multiple of $7$? Yes, $14 = 2 \times 7$.
So, $25 \equiv 11 \pmod{7}$ is true.

4. Key Takeaways

• Modulo arithmetic is about finding the remainder of a division.
• The modulus is the number you're dividing by.
• $a \pmod{n}$ gives you the unique remainder, which will always be between $0$ and $n-1$.
• Congruence $a \equiv b \pmod{n}$ means $a$ and $b$ have the same remainder when divided by $n$.
• An easy way to check congruence is if $a - b$ is a multiple of $n$.
• Modulo arithmetic is fundamental in computer science (hashing, cryptography) and telling time.

Common mistakes to avoid:
- Forgetting that the remainder $r$ must satisfy $0 \le r < n$.
- Confusing $a \pmod{n}$ (the result, a single number) with $a \equiv b \pmod{n}$ (a statement of relationship).
- Incorrectly handling negative numbers in modulo operations (different languages can have slightly different behaviors, but mathematically, $-10 \pmod{3}$ is $2$, not $-1$).
- Assuming congruence means the numbers are equal; they just behave similarly under division by the modulus.

5. Now Try It

Exercise: Determine which of the following statements are true:
1. $30 \pmod{7}$
2. $19 \equiv 5 \pmod{7}$
3. $-3 \equiv 4 \pmod{7}$ (Hint: Think about what number added to $-3$ would be a multiple of $7$, or what $-3$ "looks like" on a clock face counting backward from $0$.)

Once you've done the calculations, success looks like having the correct remainder for the first one, and correctly identifying true/false for the congruence statements with clear reasoning for each.