Euler's Totient Function (φ)

About Euler's Totient Function

Euler's totient function φ(n) counts the number of integers between 1 and n that are coprime to n (their greatest common divisor with n is 1).

Properties:

• For a prime number p, φ(p) = p - 1
• For prime powers p^k, φ(p^k) = p^k - p^k-1
• The function is multiplicative: if gcd(m,n) = 1, then φ(mn) = φ(m)φ(n)

Formula:

For a number n with prime factorization n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ:
φ(n) = n × ∏(1 - 1/pᵢ)

Applications:

• Cryptography (RSA algorithm)
• Modular arithmetic
• Number theory
• Group theory