Euler Phi Function: φ(n)

euler-totient, Euler Phi Function, Euler Totient Function, Euler's Totient, 오일러 파이, 오일러 토션

정의

Euler Phi Function φ(n) 은 1 이상 n 이하 정수 중 n 과 서로소인 정수의 개수.

기존 Euler Phi 위키 참조. 이 페이지는 alias 확장용 축약.

공식

• 소수 p: φ(p) = p - 1
• p^k: φ(p^k) = p^k - p^(k-1)
• 곱셈적: gcd(a, b) = 1 이면 φ(ab) = φ(a)φ(b)
• 일반: φ(n) = n · Π (1 - 1/p) over distinct primes p | n

참고

• Euler Phi (본 위키)
• Euler Totient
• Fermat’s Little Theorem