+
편집 토론 역사 역링크 설정

오일러 피 함수

최근 수정 시각 : 2023-05-23 19:32:42 | 조회수 : 54
오일러 파이 함수 ➤ 오일러 피 함수
Euler totient function, ϕ(n)\phi(n)

주어진 자연수 nn보다 작은 자연수 중 nn과 서로소인 개수를 세는 수론적 함수이다.

목차

1. 정의
2. 성질
2.1. 약수들에 대한 함숫값의 합으로의 표현
2.1.1. 증명
2.2. 곱 형태의 표현
2.2.1. 증명
2.3. 약수들에 대한 함숫값의 합
2.3.1. 증명
2.4. 하한
2.4.1. 증명
2.5. 기타
2.5.1. 증명
3. 영상

1. 정의 ✎ ⊖

오일러 파이 함수는 nn 이하의 자연수 중에서 nn과 서로소인 것의 갯수로 정의된다.
  • ϕ(n)=#{k≤n:(n,k)=1}\phi(n)=\# \{k\le n : (n,k)=1\}
이는 다음과 같이 나타낼 수도 있다.
  • ϕ(n)=∑a≤n,(a,n)=11\phi(n)=\sum_{a \leq n, (a,n)=1}1
다음과 같이 표기하는 서적도 있다.
  • ϕ(n)=∑k=1n1\phi(n) = \sum_{k=1}^n 1

2. 성질 ✎ ⊖

2.1. 약수들에 대한 함숫값의 합으로의 표현 ✎ ⊖

ϕ(n)=∑d∣nμ(d)nd\phi(n)=\sum_{d \mid n}\mu(d)\frac{n}{d}

2.1.1. 증명 ✎ ⊖

ϕ(x)=∑k=1n[1(n,k)]=∑k=1n∑d∣(n,k)μ(d)=∑k=1n∑d∣n, d∣kμ(d)∑d∣q∑q=1n/dμ(d) (let. k=qd)=∑d∣nμ(d)nd\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}

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

2.2. 곱 형태의 표현 ✎ ⊖

[phi(n)=n prod_{p mid n}left(1-frac{1}{p}right)]

2.2.1. 증명 ✎ ⊖

n∏p∣n(1−1p)=n(1+∑p1∣n−1p1+∑p1∣n, p2∣n, p1≠p21p1p2+⋯ )=∑d∣nμ(d)nd=ϕ(n)\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}
이 식에서 ϕ\phi가 곱셈적이라는 것을 알 수 있다. 사실, m,n∈Nm,n \in \Bbb N에 대해 다음이 성립한다.
ϕ(mn)=ϕ(m)ϕ(n)(m,n)ϕ((m,n))\phi(mn)=\phi(m)\phi(n)\frac{(m,n)}{\phi((m,n))}
여기서 (m,n)(m,n)은 m,nm,n의 최대공약수이다.

2.3. 약수들에 대한 함숫값의 합 ✎ ⊖

[sum_{d mid n}phi(d)=n]

2.3.1. 증명 ✎ ⊖

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

nn의 약수 dd에 대하여 집합 AdA_d을 nn과의 최대공약수가 dd인 자연수들의 집합으로 정의하면, 임의의 Adi,AdjA_{d_i}, A_{d_j}은 서로소이며 ⋃d∣nAd={1,2,⋯ ,n}\bigcup_{d|n} A_d=\{1,2, \cdots, n\}이다. 그런데 ∣Ad∣=ϕ(nd)|A_d|=\phi(\frac{n}{d})이므로
∑d∣nϕ(nd)=n\sum_{d|n} \phi(\frac{n}{d})=n
따라서 원하는 결과를 얻는다.

2.4. 하한 ✎ ⊖

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

조금 더 약하게는 다음이 성립한다.
ϕ(n)≫n/log⁡log⁡n\phi(n)\gg n/\log\log n

2.4.1. 증명 ✎ ⊖

R\mathcal R을 모든 m<nm<n에 대해 ϕ(m)/m<ϕ(n)/n\phi(m)/m<\phi(n)/n인 자연수 nn의 집합으로 정의하자.

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

따라서 n∉Rn\not\in\mathcal R이 되므로 R\mathcal R의 원소는 모두 다음의 형태를 띤다.
  • n=∏p≤ypn=\prod_{p\leq y}p
log⁡\log를 취하면 log⁡n=ϑ(y)≍y\log n=\vartheta(y)\asymp y이고, 다시 log⁡\log를 취하면 log⁡log⁡n=log⁡y+O(1)\log\log n=\log y+O(1)을 얻는다.
따라서 메르텐스의 공식 ∏p≤x(1−1p)−1=eγlog⁡x+O(1)\prod_{p\leq x}\left(1-\frac1p\right)^{-1}=e^\gamma\log x+O(1)에 의해
  • ϕ(n)n=∏p≤y(1−1p)=e−γlog⁡y(1+O(1/log⁡y)){\phi(n)\over n}=\prod_{p\leq y}\left(1-\frac1p\right)={e^{-\gamma}\over\log y}(1+O(1/\log y))
가 되고, 등호가 성립한다.

n∉Rn\not\in\mathcal R일 경우, m<nm<n이고 ϕ(m)/m<ϕ(n)/n\phi(m)/m<\phi(n)/n인 m∈Rm\in\mathcal R이 존재한다. 그러면
  • ϕ(n)n>ϕ(m)m=1log⁡log⁡m(e−γ+O(1/log⁡log⁡m))≥1log⁡log⁡n(e−γ+O(1/log⁡log⁡n))\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))
가 성립한다.

따라서 증명되었다.

2.5. 기타 ✎ ⊖

  • ϕ(pa)=pa−pa−1\phi(p^a)=p^a-p^{a-1}
  • ϕ(mn)=ϕ(m)ϕ(n)((m,n)/ϕ((m,n)))\phi(mn)=\phi(m)\phi(n)((m,n)/\phi((m,n)))
  • a∣b⇒ϕ(a)∣ϕ(b)a \mid b \Rightarrow \phi(a) \mid \phi(b)
  • nn이 rr개의 서로 다른 홀소수를 가지면 2r∣ϕ(n)2^r \mid \phi(n)

2.5.1. 증명 ✎ ⊖

ϕ(n)=n∏p∣n(1−1p)\phi(n)=n \prod_{p \mid n}\left(1-\frac{1}{p}\right)에서 간단히 증명된다.

3. 영상 ✎ ⊖



이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.