Modular Arithmetic

Context: FIT1058_MOC · remainder operation $n\mathrm{mod}d$ + congruence $a\equiv b(\mathrm{mod}n)$ · an Equivalence Relation partitioning $\mathbb{Z}$ into ${\mathbb{Z}}_n$ · basis of the Euclidean Algorithm, Modular Inverse and Modular Exponentiation

Quick Revision

• 🎯 Objective: $n=qd+r$, $0\le r\le d-1$ ➔ remainder operation ⟹ congruence relation ⟹ arithmetic on $n$ residue classes.
• 📦 Core Components: $n\mathrm{mod}d$ (operation) ➔ $a\equiv b(\mathrm{mod}n)$ (relation) ➔ $+,-,\times$ on ${\mathbb{Z}}_n$.
• ⚡ Key Constraint: negative $n$ rounds the quotient down ($r\ge 0$, so $-6\mathrm{mod}5=4$); division needs a Modular Inverse.

📝 Core

1. The Modulo Operation (Division Algorithm)

• Division Algorithm ➔ unique $q,r$ with $n=qd+r$, $0\le r\le d-1$; $q=\lfloor n/d\rfloor$.
• Notation ➔ $n\mathrm{mod}d$ is an infix operation ($6\mathrm{mod}4=2$); zero remainder ⟺ $d\mid n$.
• Negative $n$ ➔ floor keeps $r\ge 0$: $-6\mathrm{mod}5=4$ (largest multiple $\le -6$ is $-10$).
• Programming caveat ➔ % agrees for non-negatives; for negatives some languages return $-1$ — % ≠ mathematical mod.

2. Congruence (the Relation)

• Three definitions ➔ $a\equiv b(\mathrm{mod}n)⟺n\mid (a-b)⟺a\mathrm{mod}n=b\mathrm{mod}n$.
• Equivalence structure ➔ reflexive/symmetric/transitive (Equivalence Relation) ⟹ partitions $\mathbb{Z}$ into $n$ classes $[a]=a+n\mathbb{Z}$.
• Operation vs relation ➔ $n\mathrm{mod}d$ returns a value; $a\equiv b$ and $d\mid n$ are true/false; link: $a\equiv b\iff a\mathrm{mod}n=b\mathrm{mod}n$.

3. Class Arithmetic on ${\mathbb{Z}}_n$

• Representative rule ➔ $[a]+[b]=[a+b]$, $[a]-[b]=[a-b]$, $xy\equiv ab(\mathrm{mod}n)$ — pick one member each, combine, reduce.
• Worked micro-example ➔ in ${\mathbb{Z}}_5$: $3+4=7\equiv 2$, $3\times 4=12\equiv 2$.
• Division ➔ does not transfer in general; needs a Modular Inverse, which exists iff the element is coprime to $n$.
• Everyday instances ➔ weekdays (mod 7), clocks (mod 24), parity toggle (mod 2), last digit (mod 10).

When It Flips: for fixed $d>0$ the pair $(q,r)$ is unique, making $\mathrm{mod}$ well-defined; replacing repeated subtraction with one $\mathrm{mod}$ is exactly the speed-up from naïve gcd to the Euclidean Algorithm.

⚠️ Common Mistakes

• 💡 $-6\mathrm{mod}5=4$, not $-1$ ➔ the floor convention forces $r\in [0,d-1]$; a language’s % might return $-1$ but mathematical mod never does.
• 💡 ${\mathbb{Z}}_n$ equation ≠ congruence ➔ ”$2+3=1$ in ${\mathbb{Z}}_4$” is an equation (the only value there); "$2+3\equiv 1(\mathrm{mod}4)$" is a congruence (also $\equiv 37$); but ”$2+3=37$ in ${\mathbb{Z}}_4$” is wrong ($37\notin {\mathbb{Z}}_4$).

🧠 Active Recall

Give three equivalent definitions of $a\equiv b(\mathrm{mod}n)$ and explain why the classes partition $\mathbb{Z}$.

• Hint: Congruence is an equivalence.

Answer

• Short answer: $n\mid (a-b)$ ⟺ $\exists k:a-b=kn$ ⟺ $a\mathrm{mod}n=b\mathrm{mod}n$.
• Why: Equivalence relation ➔ reflexive/symmetric/transitive ⟹ $n$ disjoint residue classes $[0],\dots ,[n-1]$.

Why can class arithmetic use single representatives, and how do " $2+3=1$ in ${\mathbb{Z}}_4$" and "$2+3\equiv 1(\mathrm{mod}4)$" differ?

• Hint: Well-defined operations.

Answer

• Short answer: $[a]+[b]=[a+b]$ depends only on the classes; one representative each suffices.
• Why: Equation vs congruence ➔ ${\mathbb{Z}}_4$ has only $\{0,1,2,3\}$; a congruence allows any class member ($37$), an equation does not.

Compute $-6\mathrm{mod}5$ and justify via the Division Algorithm.

• Hint: Floor the quotient.

Answer

• Short answer: $-6=(-2)\cdot 5+4$ ⟹ $-6\mathrm{mod}5=4$.
• Why: Round down ➔ $q=\lfloor -6/5\rfloor =-2$ is the largest integer with $qd\le n$, guaranteeing $0\le r\le d-1$.