오일러 파이 함수
1. 개요
'''오일러 파이 함수(Euler phi function)'''는 특수함수의 하나로, 정의는 다음과 같다.
$$\displaystyle \phi(n) \equiv \sum_{m=1}^{n} (\bold{1}_{\{1\}} \circ \gcd)(m,\,n)\quad$$($$n \in \mathbb{N}$$)
이름대로 레온하르트 오일러가 정의한 함수다. 정의에서 보듯, 특정 수 이하의 서로소의 개수를 구하는 데 쓰인다. 서로소일 경우에만 값이 증가하므로, 이 함수는 계단함수다.
몇가지 특수한 성질이 존재하는데, 그 중 하나는 '''서로소인 서로 다른 두 수 $$a,b$$'''라는 조건을 걸 경우, 정수론적 함수[1]의 성질을 지니고 있다는 점이다. 즉, 다음과 같다.
만약 $$\gcd(a,\,b)=1$$이라면, $$\phi(ab)=\phi(a)\phi(b)$$
[1] 정의역과 치역이 모두 정수, 혹은 정수의 부분집합인 함수 중에서 $$f(ab)=f(a)f(b)$$라는 성질을 지닌 함수를 의미한다.
$$\displaystyle \phi(p^n)=p^{n}-\frac{p^{n}}{p}=p^{n}\left(1-\frac{1}{p}\right)$$가 된다.
이 두 성질을 조합하면, 오일러 파이 함수는 다음과 같은 수단으로 구할 수 있다는 것을 알 수 있다.$$\displaystyle a=\prod_{i=1}^n p_{i}^{k_{i}}$$의 형태로 소인수분해할 수 있다고 두면
$$\displaystyle \phi(a)=\phi\left(\prod_{i=1}^n p_{i}^{k_{i}}\right)=\prod_{i=1}^n \phi(p_{i}^{k_{i}})=\prod_{i=1}^n \left[p_{i}^{k_{i}}\left(1-\frac{1}{p_i}\right)\right]$$
즉, $$\displaystyle \phi(n)= n \prod_{p|n}(1-\frac {1}{p})$$(단, $$p$$는 소수)$$\displaystyle \phi(a)=\phi\left(\prod_{i=1}^n p_{i}^{k_{i}}\right)=\prod_{i=1}^n \phi(p_{i}^{k_{i}})=\prod_{i=1}^n \left[p_{i}^{k_{i}}\left(1-\frac{1}{p_i}\right)\right]$$
또한, 뫼비우스 반전 공식(Möbius inversion formula)이 적용되기에, 뫼비우스 함수 $$\mu$$[2]를 이용하면 다음이 성립한다.
$$\displaystyle\phi(n)=\sum_{n\mid d}\mu\left(\frac{n}{d}\right)d$$