블랙핑크 갤러리 ➤ 오일러 피 함수
(+)분류 : 가져온 문서/오메가
Euler totient function, \\phi(n)
주어진 자연수 n보다 작은 자연수 중 n과 서로소인 개수를 세는 수론적 함수이다.
목차
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. 정의
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. 정의 ✎ ⊖
오일러 파이 함수는 n 이하의 자연수 중에서 n과 서로소인 것의 갯수로 정의된다.
- \\phi(n)=\\# \\{k\\le n : (n,k)=1\\}
- \\phi(n)=\\sum_{a \\leq n, (a,n)=1}1
- \\phi(n) = \\sum_{k=1}^n 1
2. 성질 ✎ ⊖
2.1. 약수들에 대한 함숫값의 합으로의 표현 ✎ ⊖
\\phi(n)=\\sum_{d \\mid n}\\mu(d)\\frac{n}{d}
2.1.1. 증명 ✎ ⊖
\\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}
\\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. 증명 ✎ ⊖
\\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 \\in \\Bbb N에 대해 다음이 성립한다.
\\phi(mn)=\\phi(m)\\phi(n)\\frac{(m,n)}{\\phi((m,n))}
여기서 (m,n)은 m,n의 최대공약수이다.
2.3. 약수들에 대한 함숫값의 합 ✎ ⊖
[sum_{d mid n}phi(d)=n]
2.3.1. 증명 ✎ ⊖
\\phi(n)=\\sum_{d \\mid n}\\mu(d)\\frac{n}{d}에서 뫼비우스 반전을 이용하면 간단하게 증명되지만, 이렇게 증명할 수도 있다.
n의 약수 d에 대하여 집합 A_d을 n과의 최대공약수가 d인 자연수들의 집합으로 정의하면, 임의의 A_{d_i}, A_{d_j}은 서로소이며 \\bigcup_{d|n} A_d=\\{1,2, \\cdots, n\\}이다. 그런데 |A_d|=\\phi(\\frac{n}{d})이므로
따라서 원하는 결과를 얻는다.
n의 약수 d에 대하여 집합 A_d을 n과의 최대공약수가 d인 자연수들의 집합으로 정의하면, 임의의 A_{d_i}, A_{d_j}은 서로소이며 \\bigcup_{d|n} A_d=\\{1,2, \\cdots, n\\}이다. 그런데 |A_d|=\\phi(\\frac{n}{d})이므로
\\sum_{d|n} \\phi(\\frac{n}{d})=n
따라서 원하는 결과를 얻는다.
2.4. 하한 ✎ ⊖
n\\geq3에 대해 다음이 성립한다.
\\phi(n)\\ge{n\\over\\log\\log n}(e^{-\\gamma}+O(1/\\log\\log n))
또한 위 식에서 등호가 성립하는 n이 무한히 많이 존재한다.
여기서 \\gamma는 오일러 상수이다.
조금 더 약하게는 다음이 성립한다.
\\phi(n)\\ge{n\\over\\log\\log n}(e^{-\\gamma}+O(1/\\log\\log n))
또한 위 식에서 등호가 성립하는 n이 무한히 많이 존재한다.
여기서 \\gamma는 오일러 상수이다.
조금 더 약하게는 다음이 성립한다.
\\phi(n)\\gg n/\\log\\log n
2.4.1. 증명 ✎ ⊖
\\mathcal R을 모든 m<n에 대해 \\phi(m)/m<\\phi(n)/n인 자연수 n의 집합으로 정의하자.
\\omega(n)=k (n의 서로 다른 소인수의 개수)에 대해 n^*를 첫 k개 소수의 곱으로 두면, n\\neq n^*일 경우 n^*<n, \\phi(n^*)/n^*<\\phi(n)/n이 성립한다.
따라서 n\\not\\in\\mathcal R이 되므로 \\mathcal R의 원소는 모두 다음의 형태를 띤다.
따라서 메르텐스의 공식 \\prod_{p\\leq x}\\left(1-\\frac1p\\right)^{-1}=e^\\gamma\\log x+O(1)에 의해
n\\not\\in\\mathcal R일 경우, m<n이고 \\phi(m)/m<\\phi(n)/n인 m\\in\\mathcal R이 존재한다. 그러면
따라서 증명되었다.
\\omega(n)=k (n의 서로 다른 소인수의 개수)에 대해 n^*를 첫 k개 소수의 곱으로 두면, n\\neq n^*일 경우 n^*<n, \\phi(n^*)/n^*<\\phi(n)/n이 성립한다.
따라서 n\\not\\in\\mathcal R이 되므로 \\mathcal R의 원소는 모두 다음의 형태를 띤다.
- n=\\prod_{p\\leq y}p
따라서 메르텐스의 공식 \\prod_{p\\leq x}\\left(1-\\frac1p\\right)^{-1}=e^\\gamma\\log x+O(1)에 의해
- {\\phi(n)\\over n}=\\prod_{p\\leq y}\\left(1-\\frac1p\\right)={e^{-\\gamma}\\over\\log y}(1+O(1/\\log y))
n\\not\\in\\mathcal R일 경우, m<n이고 \\phi(m)/m<\\phi(n)/n인 m\\in\\mathcal R이 존재한다. 그러면
- \\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. 기타 ✎ ⊖
- \\phi(p^a)=p^a-p^{a-1}
- \\phi(mn)=\\phi(m)\\phi(n)((m,n)/\\phi((m,n)))
- a \\mid b \\Rightarrow \\phi(a) \\mid \\phi(b)
- n이 r개의 서로 다른 홀소수를 가지면 2^r \\mid \\phi(n)
2.5.1. 증명 ✎ ⊖
\\phi(n)=n \\prod_{p \\mid n}\\left(1-\\frac{1}{p}\\right)에서 간단히 증명된다.