오일러 피 함수

블랙핑크 갤러리 ➤ 오일러 피 함수

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. 정의 _{✎ ⊖}

오일러 파이 함수는 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]

\\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

따라서 원하는 결과를 얻는다.

2.4. 하한 _{✎ ⊖}

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

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의 원소는 모두 다음의 형태를 띤다.

n=\\prod_{p\\leq y}p

\\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))

가 성립한다.

따라서 증명되었다.

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)에서 간단히 증명된다.

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. 정의 _{✎ ⊖}

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. 영상 _{✎ ⊖}