정의 오일러 함수 \phi (n)(때로는 \varphi(n) 또는 {\it phi}(n)으로 표기합니다)은 1부터 n까지의 수 중 n과 서로소인 수의 개수입니다. 다시 말해, 이는 구간 [1; n]에 속하는 수 중 n과의 최대공약수가 1인 수의 개수입니다.
이 함수의 처음 몇 개의 값은 다음과 같습니다(OEIS 백과사전의 A000010):
\phi (1)=1, \phi (2)=1, \phi (3)=2, \phi (4)=2, \phi (5)=4.
성질 오일러 함수의 다음 세 가지 간단한 성질만 알면 임의의 수에 대해 이 함수를 계산할 수 있습니다:
p가 소수이면 \phi (p)=p-1입니다. (p 자신을 제외한 모든 수는 p와 서로소이므로 이는 자명합니다.)
p가 소수이고 a가 자연수이면 \phi (p^a)=p^a-p^{a-1}입니다. (p^a와 서로소가 아닌 수는 pk (k \in \mathcal{N}) 꼴의 수뿐이며, 그러한 수는 p^a / p = p^{a-1}개이기 때문입니다.)
a와 b가 서로소이면 \phi(ab) = \phi(a) \phi(b)입니다(오일러 함수의 “곱셈성”). (이 사실은 중국인의 나머지 정리로부터 도출됩니다. 임의의 수 z \le ab를 생각해 봅시다. z를 a와 b로 나눈 나머지를 각각 x와 y라고 합시다. 그러면 z가 ab와 서로소인 것은 z가 a 및 b와 각각 서로소인 것과 동치이며, 이는 x가 a와 서로소이고 y가 b와 서로소인 것과 같습니다. 중국인의 나머지 정리를 적용하면, 임의의 수의 쌍 x와 y (x \le a, ~ y \le b)에 수 z (z \le ab)가 일대일로 대응한다는 것을 얻으며, 이로써 증명이 완료됩니다.)
따라서 임의의 \it n에 대한 오일러 함수는 그 인수분해(n을 소인수들로 분해한 것)를 통해 구할 수 있습니다:
다음과 같을 때
n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot […]
(여기서 모든 p_i는 소수입니다), 그러면
\phi(n) = \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) […] = (p_1^{a_1} - p_1^{a_1-1}) \cdot (p_2^{a_2} - p_[…] = n \cdot \left( 1-{1\over p_1} \right) \cdot \le[…]
구현 오일러 함수를 계산하는 가장 간단한 코드로, 수를 기본적인 방법으로 O (\sqrt n)에 소인수분해합니다:
int phi (int n) { int result = n; for (int i=2; i*i<=n; ++i) if (n % i == 0) { while (n % i == 0) n /= i; result -= result / i; } if (n > 1) result -= result / n; return result; } 오일러 함수 계산의 핵심은 수 n의 소인수분해를 구하는 것입니다. 이는 O(\sqrt{n})보다 훨씬 짧은 시간에 수행할 수 있습니다. 다음을 참고하십시오. 효율적인 소인수분해 알고리즘.
오일러 함수의 응용 오일러 함수의 가장 유명하고 중요한 성질은 오일러 정리로 표현됩니다:
a^{\phi(m)} \equiv 1 \pmod m,
여기서 \it a와 \it m은 서로소입니다. 특수한 경우로, \it m이 소수일 때 오일러 정리는 이른바 페르마의 소정리가 됩니다:
a^{m-1} \equiv 1 \pmod m
오일러 정리는 실제 응용에서 꽤 자주 등장합니다. 예를 들어 다음을 참고하십시오. 모듈러 연산에서의 모듈러 역원.