Euler’s Theorem and Fermat’s Little Theorem

Context: FIT1058_MOC · $x^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ for coprime $x$ · prime case $x^{p-1}\equiv 1$ · lets exponents be reduced mod $\varphi (n)$

Quick Revision

• 🎯 Objective: $\gcd (x,n)=1\Rightarrow x^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ ➔ FLT is the prime case $x^{p-1}\equiv 1$.
• 📦 Core Components: Euler ➔ FLT (prime) ➔ reduce exponents mod $\varphi (n)$.
• ⚡ Key Constraint: requires coprimality; the practical payoff is shrinking exponents in Modular Exponentiation.

📝 Core

1. The Theorems

• Euler ➔ $\gcd (x,n)=1\Rightarrow x^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.
• FLT ➔ prime case $n=p$: $x^{p-1}\equiv 1(\mathrm{mod}p)$ (using $\varphi (p)=p-1$).
• Relationship ➔ FLT is Euler at a prime modulus.

2. Why It Holds

• ${\mathbb{Z}}_n^{\ast }$ is a group ➔ closed, associative, identity 1, inverses.
• Group fact ➔ any element${}^{|\text{group}|}$ = identity ⟹ $x^{\varphi (n)}\equiv 1$.

3. Exponent Reduction

• Rule ➔ $x\equiv y(\mathrm{mod}\varphi (n))\Rightarrow a^x\equiv a^y(\mathrm{mod}n)$ (for $\gcd (a,n)=1$).
• Examples ➔ $2^9\equiv 2^{9\mathrm{mod}6}=2^3\equiv 1(\mathrm{mod}7)$; $3^{36}\equiv 3^{16}\equiv 21(\mathrm{mod}25)$.

Key identities:

$\gcd (x,n)=1\Rightarrow x^{\varphi (n)}\equiv 1(\mathrm{mod}n);x^{p-1}\equiv 1(\mathrm{mod}p)(p\text{ prime})$ $a^m\equiv a^{m\mathrm{mod}\varphi (n)}(\mathrm{mod}n)$

⚖️ Core Decision Matrix

Theorem	Modulus	Exponent	Condition
Euler	any $n$	$\varphi (n)$	$\gcd (x,n)=1$
FLT	prime $p$	$p-1$	$p\nmid x$
exponent rule	$n$	$m\mathrm{mod}\varphi (n)$	$\gcd (a,n)=1$

When It Flips: the theorem shrinks the exponent in Modular Exponentiation from $m$ to $m\mathrm{mod}\varphi (n)$, often turning a huge power into a small one — the algebra behind RSA and key-exchange correctness.

📊 Exam Execution Trace

Manual Execution Trace

$3^{100}\mathrm{mod}7$:

Step / State	Quantity	Value
0 (Init)	—	—
1	$\varphi (7)$	6
2	$100\mathrm{mod}6$	4
3	$3^4\mathrm{mod}7$	4

⚠️ Common Mistakes

• 💡 Coprimality required ➔ without $\gcd (x,n)=1$ the powers never reach 1 (they get stuck — see Primitive Root).

🧠 Active Recall

State Euler's theorem and FLT, and how one specialises to the other.

• Hint: Group size exponent.

Answer

• Short answer: Euler: $x^{\varphi (n)}\equiv 1$ ($\gcd =1$); FLT: $x^{p-1}\equiv 1$ ($p$ prime) — Euler at $n=p$.
• Why: ${\mathbb{Z}}_n^{\ast }$ group ➔ any element to the group size ($\varphi (n)$) is the identity.

Use the theorem to simplify $2^9\mathrm{mod}7$ and give the general exponent rule.

• Hint: Reduce exponent mod $\varphi (n)$.

Answer

• Short answer: $9\mathrm{mod}6=3$, so $2^9\equiv 2^3=8\equiv 1(\mathrm{mod}7)$; generally $a^x\equiv a^{x\mathrm{mod}\varphi (n)}$.
• Why: Workhorse ➔ replaces a large exponent by a small residue in Modular Exponentiation.