오일러 피 함수 (편집)

[[분류:가져온 문서/오메가]]
Euler totient function, [math(\phi(n))]

주어진 자연수 [math(n)]보다 작은 자연수 중 [math(n)]과 서로소인 개수를 세는 [[수론적 함수]]이다.

== 정의 ==
오일러 파이 함수는 [math(n)] 이하의 자연수 중에서 [math(n)]과 서로소인 것의 갯수로 정의된다.
* [math(\phi(n)=\# \{k\le n : (n,k)=1\})]
이는 다음과 같이 나타낼 수도 있다.
* <math>\phi(n)=\sum_{a \leq n, (a,n)=1}1</math>
다음과 같이 표기하는 서적도 있다.
* <math>\phi(n) = \sum_{k=1}^n 1</math>

== 성질 ==
=== 약수들에 대한 함숫값의 합으로의 표현 ===
[math(\phi(n)=\sum_{d \mid n}\mu(d)\frac{n}{d})]

====증명====
><math>\begin{aligned} \phi(x)&=\sum_{k=1}^{n} \left[ \frac{1}{(n,k)} \right]=\sum_{k=1}^{n} \sum_{d \mid (n,k)} \mu(d)\\&=\sum_{k=1}^{n} \sum_{d \mid n,\ d \mid k} \mu(d) \sum_{d \mid q} \sum_{q=1}^{n/d} \mu(d)\ (\text{let.}\ k=qd)\\&=\sum_{d \mid n} \mu(d) \frac{n}{d} \end{aligned}</math>

[math(\sum_{d \mid n} \mu(d) = \left[ \frac{1}{n} \right])]임은 [[뫼비우스 함수]]를 참고하라.

===곱 형태의 표현===
\[\phi(n)=n \prod_{p \mid n}\left(1-\frac{1}{p}\right)\]

==== 증명 ====
><math>\begin{aligned} n \prod_{p \mid n}\left(1-\frac{1}{p}\right)&=n(1+\sum_{p_1 \mid n} \frac{-1}{p_1}+\sum_{p_1 \mid n,\ p_2 \mid n,\ p_1 \neq p_2} \frac{1}{p_1p_2}+ \cdots)\\&=\sum_{d \mid n} \mu(d) \frac{n}{d}\\&=\phi(n) \end{aligned}</math>
이 식에서 [math(\phi)]가 곱셈적이라는 것을 알 수 있다. 사실, [math(m,n \in \Bbb N)]에 대해 다음이 성립한다.
><math>\phi(mn)=\phi(m)\phi(n)\frac{(m,n)}{\phi((m,n))}</math>
여기서 [math((m,n))]은 [math(m,n)]의 최대공약수이다.

=== 약수들에 대한 함숫값의 합 ===
\[\sum_{d \mid n}\phi(d)=n\]

====증명====
[math(\phi(n)=\sum_{d \mid n}\mu(d)\frac{n}{d})]에서 뫼비우스 반전을 이용하면 간단하게 증명되지만, 이렇게 증명할 수도 있다.

[math(n)]의 약수 [math(d)]에 대하여 집합 [math(A_d)]을 [math(n)]과의 최대공약수가 [math(d)]인 자연수들의 집합으로 정의하면, 임의의 [math(A_{d_i}, A_{d_j})]은 서로소이며 [math(\bigcup_{d|n} A_d=\{1,2, \cdots, n\})]이다. 그런데 [math(|A_d|=\phi(\frac{n}{d}))]이므로
><math>\sum_{d|n} \phi(\frac{n}{d})=n</math>
따라서 원하는 결과를 얻는다.

=== 하한 ===
[math(n\geq3)]에 대해 다음이 성립한다.
[math(\phi(n)\ge{n\over\log\log n}(e^{-\gamma}+O(1/\log\log n)))]
또한 위 식에서 등호가 성립하는 [math(n)]이 무한히 많이 존재한다.
여기서 [math(\gamma)]는 [[오일러 상수]]이다.

조금 더 약하게는 다음이 성립한다.
><math>\phi(n)\gg n/\log\log n</math>

====증명====
[math(\mathcal R)]을 모든 [math(m<n)]에 대해 [math(\phi(m)/m<\phi(n)/n)]인 자연수 [math(n)]의 집합으로 정의하자.

[math(\omega(n)=k)] (n의 서로 다른 소인수의 개수)에 대해 [math(n^*)]를 첫 [math(k)]개 소수의 곱으로 두면, [math(n\neq n^*)]일 경우 [math(n^*<n)], [math(\phi(n^*)/n^*<\phi(n)/n)]이 성립한다.

따라서 [math(n\not\in\mathcal R)]이 되므로 [math(\mathcal R)]의 원소는 모두 다음의 형태를 띤다.

* <math>n=\prod_{p\leq y}p</math>
[math(\log)]를 취하면 [math(\log n=\vartheta(y)\asymp y)]이고, 다시 [math(\log)]를 취하면 [math(\log\log n=\log y+O(1))]을 얻는다.
따라서 메르텐스의 공식 [math(\prod_{p\leq x}\left(1-\frac1p\right)^{-1}=e^\gamma\log x+O(1))]에 의해
* <math>{\phi(n)\over n}=\prod_{p\leq y}\left(1-\frac1p\right)={e^{-\gamma}\over\log y}(1+O(1/\log y))</math>
가 되고, 등호가 성립한다.

[math(n\not\in\mathcal R)]일 경우, [math(m<n)]이고 [math(\phi(m)/m<\phi(n)/n)]인 [math(m\in\mathcal R)]이 존재한다. 그러면
* [math(\displaystyle {\phi(n)\over n}>{\phi(m)\over m}={1\over\log\log m}(e^{-\gamma}+O(1/\log\log m))\ge{1\over\log\log n}(e^{-\gamma}+O(1/\log\log n)))]
가 성립한다.

따라서 증명되었다.

=== 기타 ===
* [math(\phi(p^a)=p^a-p^{a-1})]
* [math(\phi(mn)=\phi(m)\phi(n)((m,n)/\phi((m,n))))]
* [math(a \mid b \Rightarrow \phi(a) \mid \phi(b))]
* [math(n)]이 [math(r)]개의 서로 다른 홀소수를 가지면 [math(2^r \mid \phi(n))]

==== 증명 ====
[math(\phi(n)=n \prod_{p \mid n}\left(1-\frac{1}{p}\right))]에서 간단히 증명된다.

== 영상 ==
[youtube(96OEN2c28So)]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)