오일러 파이 함수

$\phi(n)$의 정의

$\phi(n)$은 n보다 작으면서 n과 서로 소인 정수의 개수를 뜻한다.

즉, $\Z_{n}*$에 속하는 원소의 개수를 뜻한다.

$\phi(n)$의 성질

• $\phi(1) = 0$

• $\phi(p) = p - 1$(p: prime number)
  소수는 어떤 1과 자신을 제외한 다른 어떤 자연수로도 나눌 수 없는 1보다 큰 자연수이므로 당연한 성질이다.
  EX) $\phi(13) = 12$

• $\phi(m*n) = \phi(m) * \phi(n)$(m, n: coprime)
  EX) $\phi(10) = \phi(2 * 5) = 4$

• $\phi(p^{e}) = p^{e} - p^{e-1}$(p: prime number)
  EX) $\phi(240) = \phi(2^{4}*3*5) = (2^{4}-2^{3})*2*4 = 64$

$\phi(n)$에 관한 오일러 정리

• $a^{\phi(n)} \equiv 1 (\mod n)$(a, n: coprime)

• $a^{k*\phi(n)+1} \equiv a (\mod n)$(k가 정수 이고, a < n)