Euler Totient Function

Context: FIT1058_MOC · $\varphi (n)=$ count of integers in $[1,n)$ coprime to $n$ · $=|{\mathbb{Z}}_n^{\ast }|$ · multiplicative, computed from the prime factorisation

Quick Revision

• 🎯 Objective: $\varphi (n)$ counts integers in $[1,n)$ coprime to $n$ ➔ $=|{\mathbb{Z}}_n^{\ast }|$, the invertible elements.
• 📦 Core Components: $\varphi (p)=p-1$ ➔ $\varphi (p^m)=p^{m-1}(p-1)$ ➔ multiplicative.
• ⚡ Key Constraint: easy with the factorisation, as hard as factoring without it.

📝 Core

1. The Function

• Definition ➔ $\varphi (n)=|\{x:0<x<n,\gcd (x,n)=1\}|=|{\mathbb{Z}}_n^{\ast }|$.
• Meaning ➔ the count of elements of ${\mathbb{Z}}_n$ with a Modular Inverse.
• Examples ➔ $\varphi (6)=2$ ($\{1,5\}$), $\varphi (7)=6$.

2. The Three Rules

• Primes ➔ $\varphi (p)=p-1$ (max, attained iff $n$ prime).
• Prime powers ➔ $\varphi (p^m)=p^{m-1}(p-1)$.
• Multiplicative ➔ $\gcd (a,b)=1\Rightarrow \varphi (ab)=\varphi (a)\varphi (b)$ ($n=pq\Rightarrow (p-1)(q-1)$, RSA).

3. Product Formula

• From factorisation ➔ $\varphi (n)=n{\prod }_{p\mid n}(1-\frac{1}{p})$ over distinct primes.

Key identities:

$\varphi (p)=p-1,\varphi (p^m)=p^{m-1}(p-1),\varphi (ab)=\varphi (a)\varphi (b)(\gcd (a,b)=1)$ $\varphi (150)=150(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=40$

⚖️ Core Decision Matrix

$n$	$\varphi (n)$	Note
prime $p$	$p-1$	maximum
$p^m$	$p^{m-1}(p-1)$	prime power
$pq$ (distinct)	$(p-1)(q-1)$	RSA
general	$n\prod (1-\frac{1}{p})$	from factorisation

When It Flips: $\varphi (n)=|{\mathbb{Z}}_n^{\ast }|$ is the size of the multiplicative group — the exponent in Euler's theorem and the order of a generator. Easy given the factorisation, hard without — the asymmetry RSA rests on.

📊 Exam Execution Trace

Manual Execution Trace

$\varphi (360)$, $360=2^3\cdot 3^2\cdot 5$:

Step / State	Prime power	$\varphi (p^k)=p^{k-1}(p-1)$
0 (Init)	—	—
1	$2^3$	$4$
2	$3^2$	$6$
3	$5$	$4$

⚠️ Common Mistakes

• 💡 “Multiplicative” needs coprimality ➔ $\varphi (ab)=\varphi (a)\varphi (b)$ only when $\gcd (a,b)=1$, not for all $a,b$; the product ranges over distinct primes.

🧠 Active Recall

State the three rules for $\varphi$ and compute $\varphi (150)$.

• Hint: Prime power + multiplicativity.

Answer

• Short answer: $\varphi (p)=p-1$, $\varphi (p^m)=p^{m-1}(p-1)$, multiplicative; $\varphi (150)=1\cdot 2\cdot 20=40$.
• Why: Product formula ➔ $150(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=40$.

Why is $\varphi (n)$ easy given the factorisation but believed hard in general?

• Hint: Factoring-hard.

Answer

• Short answer: The rules assemble $\varphi$ from the prime factorisation; without it, computing $\varphi (n)$ is as hard as factoring.
• Why: Crypto asymmetry ➔ the legitimate party knows the factors, an attacker does not.