오일러 피 함수

오일러 피 함수(Euler's phi function) 또는 오일러 파이 함수 \(\phi(n)\)이란 어떤 자연수 \(n\)보다 작거나 같은 자연수 중에서 \(n\)과 서로소인 것의 개수를 나타내는 함수이다. 예를 들어, \(\phi(8)=∣\{1,3,5,7\}∣=4\)이다. 이것을 수식으로 표현하면 다음과 같다: [math] \phi(n)=∣\{a\in \mathbb{N}|1\le a\le n,\;(a,n)=1\}∣.[/math]

성질

\(p\)는 소수라고 하자.

• \(\phi(p)=p−1\).
  • 역으로, \(\phi(n)=n−1\)이라면, \(n\)은 소수이다.
• \(\phi(p^a)=p^a−p^{a−1}\).
• \((m,n)=1\)이라면, \(\phi(mn)=\phi(m)\phi(n)\)이다. (오일러 피 함수는 곱셈적 함수이다.)
  • 이 성질을 이용하면 어떤 자연수 \(n\)의 소인수 분해가 \(n={p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k}\)라면, \(\phi(n)\)을 다음과 같이 표현할 수 있다: [math]\phi(n)=n\prod_{i=1}^k\left(1−\frac{1}{p_i}\right).[/math]

같이 보기

• 오일러의 정리
• 곱셈적 함수