Euler's Totient Function (1) 썸네일형 리스트형 54. Euler's Totient Function 오일러 토션트 함수(Euler's Totient Function)는 모듈러 곱셈 역원이 존재하는 수의 개수를 구하는 함수이며, 기호로는 $\phi$를 사용한다. 즉, 임의의 양의 정수 $n$에 대해 $\phi(n)$은 $n$ 이하의 양의 정수 중 $n$과 서로소인 것의 개수와 같다. 오일러 피(파이) 함수(Euler's Phi Function)라고도 한다. 오일러 토션트 함수의 결과값은 다음과 같은 두 가지 공식을 이용하여 구할 수 있다. $p$가 소수이고 $n = p^k$일 때, $\phi(n)=p^{k-1}(p-1)$이다. $n$과 $m$이 서로소일 때, $\phi(nm) = \phi(n) \phi(m)$이다. $n$의 소인수를 중복 없이 나열한 결과가 $p_1, p_2, \ldots, p_k$일 때.. 이전 1 다음
