🔢

Euler's Totient Function

★★★☆☆High School

📖Definition

Euler's totient function φ(n) counts positive integers up to n that are coprime to n. It's central to RSA cryptography.

φ(n) = |k : 1 ≤ k ≤ n, gcd(k,n) = 1|

Definition of Euler's totient

φ(p) = p - 1

For prime p

φ(p^k) = p^k-1(p-1)

For prime power

φ(mn) = φ(m)φ(n) if gcd(m,n) = 1

Multiplicative property

예제 1

Find φ(12).

예제 2

Find φ(100).

Discovered by: Leonhard Euler (1763)

Euler introduced this function while generalizing Fermat's little theorem.

RSA key generation

Euler's theorem, primitive roots

Order of cyclic groups

#오일러#피함수#totient#phi function