[include(틀:정수론)] [include(틀:특수함수의 목록)] == 개요 == '''오일러 파이 함수(Euler phi function)'''는 [[특수함수]]의 하나로, 정의는 다음과 같다. {{{#!wiki style="text-align: center" [br][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만을 원소로 갖는 집합의 [[집합 판별 함수|판별 함수]]이다. 이름대로 [[레온하르트 오일러]]가 정의한 함수다. 정의에서 보듯, 특정 수 이하의 서로소의 개수를 구하는 데 쓰인다. 서로소일 경우에만 값이 증가하므로, 이 함수는 [[계단(동음이의어)#s-6|계단함수]]다. 몇가지 특수한 성질이 존재하는데, 그 중 하나는 '''서로소인 서로 다른 두 수 [math(a,b)]'''라는 조건을 걸 경우, 정수론적 함수[* 정의역과 치역이 모두 정수, 혹은 정수의 부분집합인 함수 중에서 [math(f(ab)=f(a)f(b))]라는 성질을 지닌 함수를 의미한다.]의 성질을 지니고 있다는 점이다. 즉, 다음과 같다. {{{#!wiki style="text-align: center" [br]만약 [math(\gcd(a,\,b)=1)]이라면, [math(\phi(ab)=\phi(a)\phi(b))]}}} 또, '''임의의 [[소수(수론)|소수]] [math(p)]'''에 대하여, [math(\phi(p^n))]은 [math(1\leq a\leq p^n)]인 [math(a)]중 [math(p^n)]과 서로소인 수의 개수이며, [math(p^n)]는 [math(p)]만을 소인수로 가지기 때문에 자동적으로 {{{#!wiki style="text-align: center" [math(\displaystyle \phi(p^n)=p^{n}-\frac{p^{n}}{p}=p^{n}\left(1-\frac{1}{p}\right))]가 된다.}}} 이 두 성질을 조합하면, 오일러 파이 함수는 다음과 같은 수단으로 구할 수 있다는 것을 알 수 있다. {{{#!wiki style="text-align: center" [math(\displaystyle a=\prod_{i=1}^n p_{i}^{k_{i}})]의 형태로 소인수분해할 수 있다고 두면 [math(\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])]}}} 즉, [math(\displaystyle \phi(n)= n \prod_{p|n}(1-\frac {1}{p}))](단, [math(p)]는 소수) 또한, 뫼비우스 반전 공식(Möbius inversion formula)이 적용되기에, [[뫼비우스 함수]] [math(\mu)][* 주어진 수가 소수의 거듭제곱을 인수로 가지고 있는지를 판정하는 함수다. 거듭제곱을 인수로 가지고 있다면 0, 거듭제곱이 없다면 '''[[소인수]]의 개수''', 즉 [[소인수 계량 함수]]를 따져서 [math(\mu(n)=\left(-1\right)^{\omega(n)})]가 된다.]를 이용하면 다음이 성립한다. {{{#!wiki style="text-align: center" [math(\displaystyle\phi(n)=\sum_{n\mid d}\mu\left(\frac{n}{d}\right)d)]}}} [[분류:비초등함수]][[분류:정수론]][[분류:나무위키 수학 프로젝트]]