Processing math: 100%

본문 바로가기

Euler's Phi Function

(1)

54. Euler's Totient Function 오일러 토션트 함수(Euler's Totient Function)는 모듈러 곱셈 역원이 존재하는 수의 개수를 구하는 함수이며, 기호로는

$\phi$ 를 사용한다. 즉, 임의의 양의 정수

$\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$ 일 때..

티스토리툴바