Modular Inverse

Context: FIT1058_MOC · division in ${\mathbb{Z}}_n$ · $x^{-1}$ exists iff $x$ is coprime to $n$ · found via the Extended Euclidean Algorithm

Quick Revision

• 🎯 Objective: $x^{-1}$ with $x{x}^{-1}\equiv 1(\mathrm{mod}n)$ ➔ division in ${\mathbb{Z}}_n$ = multiply by the inverse.
• 📦 Core Components: exists iff $\gcd (x,n)=1$ ➔ ${\mathbb{Z}}_n^{\ast }$ ➔ computed by Extended Euclidean Algorithm.
• ⚡ Key Constraint: prime modulus ⟹ every nonzero element invertible (a field).

📝 Core

1. The Inverse

• Definition ➔ $x^{-1}$ with $x{x}^{-1}\equiv 1(\mathrm{mod}n)$ — the modular reciprocal.
• Division ➔ dividing means multiplying by the inverse.
• Examples ➔ ${\mathbb{Z}}_7$: $2^{-1}=4$; ${\mathbb{Z}}_6$: only $1,5$ invertible.

2. Existence Theorem

• Iff coprime ➔ $x$ invertible in ${\mathbb{Z}}_n\iff \gcd (x,n)=1$.
• Forward ➔ $x{x}^{-1}+kn=1$ ⟹ Bézout ⟹ coprime.
• Backward ➔ coprime ⟹ $yx+zn=1$ ⟹ $x^{-1}=y\mathrm{mod}n$.

3. Computing It

• Method ➔ run Extended Euclidean Algorithm on $x,n$; if $\gcd =1$, inverse $=y\mathrm{mod}n$.
• Sets ➔ ${\mathbb{Z}}_6^{\ast }=\{1,5\}$, ${\mathbb{Z}}_7^{\ast }=\{1,\dots ,6\}$.

⚖️ Core Decision Matrix

Element	Invertible in ${\mathbb{Z}}_n$?	Reason
$0$	never	$\gcd (0,n)=n$
$1$	always (self)	$\gcd =1$
$x$, $\gcd (x,n)=1$	yes	Bézout
$x$ sharing a factor	no	$\gcd >1$

When It Flips: invertibility is governed entirely by Coprimality with $n$; $|{\mathbb{Z}}_n^{\ast }|=\varphi (n)$ (Euler Totient Function). The inverse, when it exists, is unique in ${\mathbb{Z}}_n$.

📊 Exam Execution Trace

Manual Execution Trace

$3^{-1}$ in ${\mathbb{Z}}_7$:

Step / State	$z$	$3z\mathrm{mod}7$	Inverse?
0 (Init)	—	—	—
1	1	3	no
2	3	2	no
3	5	1	yes

⚠️ Common Mistakes

• 💡 $0$ never invertible, prime modulus special ➔ if $n=p$ prime, every nonzero element is coprime to $p$ ⟹ all invertible (${\mathbb{Z}}_p^{\ast }=\{1,\dots ,p-1\}$, a field); composite $n$ leaves some elements non-invertible.

🧠 Active Recall

For which $x$ does an inverse exist in ${\mathbb{Z}}_n$, and why does ${\mathbb{Z}}_6$ lack one for 2 while ${\mathbb{Z}}_7$ has one for every nonzero element?

• Hint: Coprimality condition.

Answer

• Short answer: Invertible iff $\gcd (x,n)=1$; $\gcd (2,6)=2$ (none), but every nonzero mod 7 is coprime.
• Why: Prime field ➔ ${\mathbb{Z}}_p^{\ast }=\{1,\dots ,p-1\}$.

How do you actually compute $x^{-1}$ in ${\mathbb{Z}}_n$?

• Hint: Extended Euclid.

Answer

• Short answer: Run EEA on $x,n$; if $\gcd =1$ it gives $yx+zn=1$, so $x^{-1}=y\mathrm{mod}n$.
• Why: Constructive Bézout ➔ turns the existence proof into an algorithm.