오일러 피 함수

n이 양의 정수일 때, n과 서로소인 1부터 n까지의 정수의 개수.

\[\phi(n)\]

 

p가 소수이면,

\[\phi(p^{k}) = p^{k-1}(p-1)\]

 

또한, 오일러 피 함수는 곱셈적 함수이므로, 다음이 성립.

\[\phi(mn) = \phi(m)\phi(n)\]