1. 개요
오일러 파이 함수(Euler phi function)는 특수함수의 하나로, 정의는 다음과 같다.
[math(displaystyle phi(n) equiv sum_{m=1}^{n} (bold{1}_{{1}} circ gcd)(m,,n)quad)]([math(n in mathbb{N})])
위에서 [math(gcd)]는 최대공약수, [math(bold{1}_{{1}})]는 서로소만을 취하기 위한 1만을 원소로 갖는 집합의 판별 함수이다.
이름대로 레온하르트 오일러가 정의한 함수다. 정의에서 보듯, 특정 수 이하의 서로소의 개수를 구하는 데 쓰인다. 서로소일 경우에만 값이 증가하므로, 이 함수는 계단함수다.
몇가지 특수한 성질이 존재하는데, 그 중 하나는 서로소인 서로 다른 두 수 [math(a,b)]라는 조건을 걸 경우, 정수론적 함수[1]라는 성질을 지닌 함수를 의미한다.]의 성질을 지니고 있다는 점이다. 즉, 다음과 같다.
만약 [math(gcd(a,,b)=1)]이라면, [math(phi(ab)=phi(a)phi(b))]
또, 임의의 소수 [math(p)]에 대하여, [math(phi(p^n))]은 [math(1leq aleq p^n)]인 [math(a)]중 [math(p^n)]과 서로소인 수의 개수이며, [math(p^n)]는 [math(p)]만을 소인수로 가지기 때문에 자동적으로
이 두 성질을 조합하면, 오일러 파이 함수는 다음과 같은 수단으로 구할 수 있다는 것을 알 수 있다.
즉, [math(displaystyle phi(n)= n prod_{p|n}(1-frac {1}{p}))](단, [math(p)]는 소수)
또한, 뫼비우스 반전 공식(Möbius inversion formula)이 적용되기에, 뫼비우스 함수 [math(mu)][2]가 된다.]를 이용하면 다음이 성립한다.
[math(displaystyle phi(n) equiv sum_{m=1}^{n} (bold{1}_{{1}} circ gcd)(m,,n)quad)]([math(n in mathbb{N})])
위에서 [math(gcd)]는 최대공약수, [math(bold{1}_{{1}})]는 서로소만을 취하기 위한 1만을 원소로 갖는 집합의 판별 함수이다.
이름대로 레온하르트 오일러가 정의한 함수다. 정의에서 보듯, 특정 수 이하의 서로소의 개수를 구하는 데 쓰인다. 서로소일 경우에만 값이 증가하므로, 이 함수는 계단함수다.
몇가지 특수한 성질이 존재하는데, 그 중 하나는 서로소인 서로 다른 두 수 [math(a,b)]라는 조건을 걸 경우, 정수론적 함수[1]라는 성질을 지닌 함수를 의미한다.]의 성질을 지니고 있다는 점이다. 즉, 다음과 같다.
만약 [math(gcd(a,,b)=1)]이라면, [math(phi(ab)=phi(a)phi(b))]
또, 임의의 소수 [math(p)]에 대하여, [math(phi(p^n))]은 [math(1leq aleq p^n)]인 [math(a)]중 [math(p^n)]과 서로소인 수의 개수이며, [math(p^n)]는 [math(p)]만을 소인수로 가지기 때문에 자동적으로
[math(displaystyle phi(p^n)=p^{n}-frac{p^{n}}{p}=p^{n}left(1-frac{1}{p}right))]가 된다.
이 두 성질을 조합하면, 오일러 파이 함수는 다음과 같은 수단으로 구할 수 있다는 것을 알 수 있다.
[math(displaystyle a=prod_{i=1}^n p_{i}^{k_{i}})]의 형태로 소인수분해할 수 있다고 두면
[math(displaystyle phi(a)=phileft(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])]
[math(displaystyle phi(a)=phileft(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])]
즉, [math(displaystyle phi(n)= n prod_{p|n}(1-frac {1}{p}))](단, [math(p)]는 소수)
또한, 뫼비우스 반전 공식(Möbius inversion formula)이 적용되기에, 뫼비우스 함수 [math(mu)][2]가 된다.]를 이용하면 다음이 성립한다.
[math(displaystylephi(n)=sum_{nmid d}muleft(frac{n}{d}right)d)]