Mathematics.

elementary number theory

Euler's Totient Function

Number Theory25 minDifficulty4 out of 10

You should know: prime numbers, modular arithmetic

Overview

Euler's totient function φ(n) counts how many integers from 1 to n are coprime to n (share no common factor with it beyond 1). For a prime p every one of 1, …, p − 1 qualifies, so φ(p) = p − 1; for composite n fewer do, e.g. φ(12) = 4 (only 1, 5, 7, 11). The function is multiplicative — φ(mn) = φ(m)φ(n) when gcd(m, n) = 1 — which together with φ(pᵏ) = pᵏ − pᵏ⁻¹ lets you compute it straight from a prime factorization. Its importance comes from Euler's theorem, a^φ(n) ≡ 1 (mod n) for gcd(a, n) = 1, which generalizes Fermat's little theorem to any modulus and is the exact fact that makes RSA encryption invertible.

Intuition

φ(n) measures how many residues mod n are 'units' — invertible under multiplication. Those units form a group of size φ(n), and in any finite group raising an element to the group's size returns the identity. That single group-theory fact is Euler's theorem, a^φ(n) ≡ 1, which is why the totient count (not n itself) is the right exponent for modular arithmetic.

Formal Definition

Definition

For a positive integer n with prime factorization n = ∏ pᵢ^{kᵢ}:

φ(n)=#{ k:1≤k≤n, gcd⁡(k,n)=1 }\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}
Definition (a count)
φ(p)=p−1,φ(pk)=pk−pk−1\varphi(p) = p - 1, \qquad \varphi(p^{k}) = p^{k} - p^{k-1}
Prime powers
gcd⁡(m,n)=1 ⇒ φ(mn)=φ(m) φ(n)\gcd(m,n) = 1 \ \Rightarrow\ \varphi(mn) = \varphi(m)\,\varphi(n)
Multiplicativity
φ(n)=n∏p∣n(1−1p)\varphi(n) = n \prod_{p \mid n}\left(1 - \tfrac{1}{p}\right)
Product formula
gcd⁡(a,n)=1 ⇒ aφ(n)≡1(modn)\gcd(a,n) = 1 \ \Rightarrow\ a^{\varphi(n)} \equiv 1 \pmod{n}
Euler's theorem

Worked Examples

  1. Use φ(p^k) = p^k − p^{k−1} on each prime power and multiply (the factors are coprime).

    φ(22)=4−2=2,φ(3)=2\varphi(2^{2}) = 4 - 2 = 2, \quad \varphi(3) = 2

  2. Multiply by multiplicativity.

    φ(12)=2⋅2=4\varphi(12) = 2 \cdot 2 = 4

Answer: φ(12) = 4 (the coprime residues are 1, 5, 7, 11).

Practice Problems

Difficulty 3/10

Compute 81 mod 10.

Difficulty 2/10

What is φ(p) for a prime p, and why?

Difficulty 5/10

In RSA with n = pq (p, q distinct primes), what is φ(n), and why does the scheme rely on it staying secret?

Quiz

φ(n) counts:
For distinct primes p, q, φ(pq) equals:
Euler's theorem states that for gcd(a, n) = 1:

Summary

  • φ(n) counts integers in 1..n coprime to n; φ(p) = p − 1 and φ(pᵏ) = pᵏ − pᵏ⁻¹.
  • φ is multiplicative: φ(mn) = φ(m)φ(n) when gcd(m, n) = 1, so φ follows from the factorization.
  • Euler's theorem a^φ(n) ≡ 1 (mod n) generalizes Fermat's little theorem and underpins RSA.

References

  1. WebsiteWikipedia — Euler's totient function