Euler totient function,
\\phi(n)주어진 자연수
n보다 작은 자연수 중
n과 서로소인 개수를 세는
수론적 함수이다.
오일러 파이 함수는
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.1. 약수들에 대한 함숫값의 합으로의 표현 ✎ ⊖
\\phi(n)=\\sum_{d \\mid n}\\mu(d)\\frac{n}{d}
\\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]임은
뫼비우스 함수를 참고하라.
[phi(n)=n prod_{p mid n}left(1-frac{1}{p}right)]
\\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]
\\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})이므로
\\sum_{d|n} \\phi(\\frac{n}{d})=n
따라서 원하는 결과를 얻는다.
n\\geq3에 대해 다음이 성립한다.
\\phi(n)\\ge{n\\over\\log\\log n}(e^{-\\gamma}+O(1/\\log\\log n))또한 위 식에서 등호가 성립하는
n이 무한히 많이 존재한다.
여기서
\\gamma는
오일러 상수이다.
조금 더 약하게는 다음이 성립한다.
\\phi(n)\\gg n/\\log\\log n
\\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의 원소는 모두 다음의 형태를 띤다.
\\log를 취하면
\\log n=\\vartheta(y)\\asymp y이고, 다시
\\log를 취하면
\\log\\log n=\\log y+O(1)을 얻는다.
따라서 메르텐스의 공식
\\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))
가 성립한다.
따라서 증명되었다.
- \\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)
\\phi(n)=n \\prod_{p \\mid n}\\left(1-\\frac{1}{p}\\right)에서 간단히 증명된다.
