오일러 피 함수

3. 성질

오일러 피 함수 $\backslash phi(n)$은 1부터 $n$까지의 자연수 중에서 $n$과 서로소인 수의 개수를 나타내는 함수이다. 이 함수는 여러 중요한 성질을 가지고 있다.

• 곱셈적 성질: 오일러 피 함수는 곱셈적 함수이다. 즉, 두 정수 $m,\; n$이 서로소이면 다음이 성립한다.^[59]

• 소수 및 소수 거듭제곱에 대한 값:
• $p$가 소수일 경우, 1부터 $p-1$까지의 모든 수는 $p$와 서로소이므로 $\backslash phi(p)\; =\; p-1$이다.^[59] 예를 들어, $\backslash phi(7)\; =\; 7-1\; =\; 6$이다.
• $p$가 소수이고 $k\; \backslash ge\; 1$인 자연수일 때, $p^k$보다 작거나 같은 양의 정수 중 $p^k$와 서로소가 아닌 수는 $p$의 배수인 $p,\; 2p,\; \backslash dots,\; p^\{k-1\}p\; =\; p^k$이며, 이들은 총 $p^\{k-1\}$개이다. 따라서 $p^k$와 서로소인 수의 개수는 다음과 같다.^[59]

• 오일러 곱 공식: 위의 곱셈적 성질과 소수 거듭제곱에 대한 공식을 이용하면, 임의의 양의 정수 $n$의 소인수 분해를 이용하여 $\backslash phi(n)$ 값을 계산할 수 있다. 이를 '''오일러 곱 공식'''(Euler product formula^영어)이라고 하며, 다음과 같이 표현된다. (자세한 내용은 오일러 곱 공식 참조)

• 약수 합 공식: 레온하르트 오일러가 증명한 항등식으로, $n$의 모든 양의 약수 $d$에 대해 오일러 피 함수의 합은 $n$ 자신이 된다. (자세한 내용은 약수 합 참조)

• 오일러의 정리: 양의 정수 $a$와 $n$이 서로소일 때, 다음 합동식이 성립한다.

• 짝수성: $n\; >\; 2$인 모든 정수 $n$에 대해 $\backslash phi(n)$은 짝수이다.

3. 1. 오일러 곱 공식

3. 2. 푸리에 변환

3. 3. 약수 합

3. 4. 기타 공식

• ''p''가 소수이면, $\backslash varphi(p)\; =\; p\; -\; 1$이다.
• ''p''가 소수이고 ''k''가 자연수이면, $\backslash varphi(p^k)\; =\; p^k\; -\; p^\{k-1\}\; =\; p^\{k-1\}\; (p-1)\; =\; p^k\; \backslash left(\; 1\; -\; \backslash frac\{1\}\{p\}\; \backslash right)$이다.
• ''m'', ''n''이 서로소인 자연수이면, $\backslash varphi(mn)\; =\; \backslash varphi(m)\backslash varphi(n)$이 성립한다. 즉, 오일러 피 함수는 곱셈적 함수이다.
• 위 성질들을 이용하면 임의의 자연수 ''n''에 대한 $\backslash varphi(n)$ 값을 계산할 수 있다. ''n''의 소인수 분해가 $n\; =\; p\_1^\{e\_1\}\; p\_2^\{e\_2\}\; \backslash cdots\; p\_d^\{e\_d\}\; =\; \backslash textstyle\backslash prod\backslash limits\_\{k=1\}^d\; \{p\_k\}^\{e\_k\}$ (여기서 $p\_k$는 서로 다른 소인수)로 주어지면,

• $a\backslash mid\; b\; \backslash implies\; \backslash varphi(a)\backslash mid\backslash varphi(b)$
• $\backslash varphi(mn)\; =\; \backslash varphi(m)\backslash varphi(n)\backslash cdot\backslash frac\{d\}\{\backslash varphi(d)\}$ (여기서 $d\; =\; \backslash operatorname\{gcd\}(m,n)$는 최대공약수)
• 특히:
• $\backslash varphi\backslash left(n^m\backslash right)\; =\; n^\{m-1\}\backslash varphi(n)$
• $\backslash varphi(\backslash operatorname\{lcm\}(m,n))\backslash cdot\backslash varphi(\backslash operatorname\{gcd\}(m,n))\; =\; \backslash varphi(m)\backslash cdot\backslash varphi(n)$
• 이는 $\backslash operatorname\{lcm\}(m,n)\backslash cdot\; \backslash operatorname\{gcd\}(m,n)\; =\; m\; \backslash cdot\; n$ 공식과 비교될 수 있다 (최소공배수).
• $\backslash frac\{\backslash varphi(n)\}\{n\}=\backslash frac\{\backslash varphi(\backslash operatorname\{rad\}(n))\}\{\backslash operatorname\{rad\}(n)\}$
• 여기서 $\backslash operatorname\{rad\}(n)$은 ''n''의 근 (''n''을 나누는 모든 서로 다른 소수의 곱)이다.
• 가우스 합 공식: ''n''의 모든 양의 약수 ''d''에 대해 다음 등식이 성립한다.

• $\backslash sum\_\{1\backslash le\; k\backslash le\; n-1\; \backslash atop\; \backslash gcd(k,n)=1\}\backslash !\backslash !k\; =\; \backslash tfrac12\; n\backslash varphi(n)$ (단, $n>1$)
• 메논 항등식 (P. Kesava Menon, 1965):

• $\backslash sum\_\{d\; \backslash mid\; n\}\; \backslash frac\{\backslash mu^2(d)\}\{\backslash varphi(d)\}\; =\; \backslash frac\{n\}\{\backslash varphi(n)\}$^[20]
• $\backslash sum\_\{k=1\}^n\backslash varphi(k)\; =\; \backslash tfrac12\; \backslash left(1+\; \backslash sum\_\{k=1\}^n\; \backslash mu(k)\backslash left\backslash lfloor\backslash frac\{n\}\{k\}\backslash right\backslash rfloor^2\backslash right)\; =\backslash frac3\{\backslash pi^2\}n^2+O\backslash left(n(\backslash log\; n)^\backslash frac23(\backslash log\backslash log\; n)^\backslash frac43\backslash right)$^[21] (Walters의 결과^[22])
• 더 개선된 점근식: $\backslash sum\_\{k=1\}^n\backslash varphi(k)\; =\backslash frac3\{\backslash pi^2\}n^2+O\backslash left(n(\backslash log\; n)^\backslash frac23(\backslash log\backslash log\; n)^\backslash frac13\backslash right)$ [Liu (2016)]
• $\backslash sum\_\{k=1\}^n\backslash frac\{\backslash varphi(k)\}\{k\}\; =\; \backslash sum\_\{k=1\}^n\backslash frac\{\backslash mu(k)\}\{k\}\backslash left\backslash lfloor\backslash frac\{n\}\{k\}\backslash right\backslash rfloor=\backslash frac6\{\backslash pi^2\}n+O\backslash left((\backslash log\; n)^\backslash frac23(\backslash log\backslash log\; n)^\backslash frac43\backslash right)$^[21]
• $\backslash sum\_\{k=1\}^n\backslash frac\{k\}\{\backslash varphi(k)\}\; =\; \backslash frac\{315\backslash ,\backslash zeta(3)\}\{2\backslash pi^4\}n-\backslash frac\{\backslash log\; n\}2+O\backslash left((\backslash log\; n)^\backslash frac23\backslash right)$^[23]
• $\backslash sum\_\{k=1\}^n\backslash frac\{1\}\{\backslash varphi(k)\}\; =\; \backslash frac\{315\backslash ,\backslash zeta(3)\}\{2\backslash pi^4\}\backslash left(\backslash log\; n+\backslash gamma-\backslash sum\_\{p\backslash text\{\; prime\}\}\backslash frac\{\backslash log\; p\}\{p^2-p+1\}\backslash right)+O\backslash left(\backslash frac\{(\backslash log\; n)^\backslash frac23\}n\backslash right)$^[23]
• (여기서 $\backslash gamma$는 오일러-마스케로니 상수이다).
• ''G''를 위수 ''n''의 순환군이라고 하면, ''G''의 원소 중 위수가 ''d'' (''d''는 ''n''의 약수)인 원소는 $\backslash varphi(d)$개 존재한다. 특히, 순환군 ''G''의 생성원은 $\backslash varphi(n)$개 존재한다.
• 자연수 ''a'', ''m'' (1 ≤ ''a'' < ''m'')에 대해, 잉여류 환 $\backslash mathbb\{Z\}/m\backslash mathbb\{Z\}$의 원소 $a\; +\; m\backslash mathbb\{Z\}$가 단원(곱셈에 대한 역원이 존재)일 필요충분조건은 ''a''와 ''m''이 서로소인 것이다. 따라서, $(\backslash mathbb\{Z\}/m\backslash mathbb\{Z\})^\backslash times$ (기약 잉여류 군)의 원소 개수는 $\backslash varphi(m)$과 같다.
• $\backslash varphi(m)\; =\; |(\backslash mathbb\{Z\}/m\backslash mathbb\{Z\})^\backslash times|$
• 이는 오일러 정리 $a^\{\backslash varphi(m)\}\; \backslash equiv\; 1\backslash pmod\; m$ (단, $\backslash gcd(a,\; m)\; =\; 1$)를 함의한다.
• 또한, 1의 ''m''제곱근 중 원시적인 것을 $\backslash zeta\_m$이라 할 때, 원분체 $\backslash mathbb\{Q\}(\backslash zeta\_m)$의 $\backslash mathbb\{Q\}$에 대한 갈루아 군은 $(\backslash mathbb\{Z\}/m\backslash mathbb\{Z\})^\backslash times$와 동형이며, 그 위수는 $\backslash varphi(m)$이다. 이는 원의 ''m''분 다항식의 차수가 $\backslash varphi(m)$임을 의미한다.
• $\backslash varphi(n)$은 $n\; \backslash ge\; 3$에 대해 짝수이다.
• 만약 ''n''이 ''r''개의 서로 다른 홀수 소인수를 가지고 있다면, $2^r\; \backslash mid\; \backslash varphi(n)$이다.
• $m\; \backslash mid\; \backslash varphi(a^m-1)$
• 모든 $a\; >\; 1$ 및 $n\; >\; 6$에 대해, $4\; \backslash nmid\; n$를 만족하는 $l\; \backslash ge\; 2n$이 존재하여 $l\; \backslash mid\; \backslash varphi(a^n\; -\; 1)$이다.

• $n\; >\; 1$이면 이다.
• 간단한 하한: $\backslash varphi(n)\; \backslash ge\; \backslash sqrt\{\backslash frac\{n\}\{2\}\}$ ($n>0$)^[61]
• 점근적 하한: ($\backslash gamma$는 오일러-마스케로니 상수)

• 점근적 성질: 임의의 $\backslash epsilon\; >\; 0$에 대해, 충분히 큰 ''n''에 대해 $\backslash varphi(n)\; >\; n^\{1\; -\; \backslash varepsilon\}$가 성립한다.^[60]
• 약수 함수 $\backslash sigma(n)$과의 관계: $n\; >\; 1$일 때,

• $\backslash varphi(n)\; =\; x$를 만족하는 자연수 ''n''이 존재하지 않는 자연수 ''x''를 노토션트라고 한다.
• 1보다 큰 모든 홀수는 노토션트이다.
• 짝수인 노토션트도 무수히 많이 존재한다.
• $\backslash varphi(n)\; =\; x$를 만족하는 ''n''이 존재한다면, 그 개수는 적어도 2개일 것으로 추측된다 (Lehmer's totient problem). (예외: $\backslash varphi(1)\; =\; \backslash varphi(2)\; =\; 1$)
• 임의의 $k\; >\; 1$에 대해, $\backslash varphi(n)\; =\; x$를 만족하는 ''n''의 개수가 정확히 ''k''개인 ''x''는 무수히 많이 존재한다.

4. 값

1부터 100까지의 오일러 피 함수 $\backslash varphi(n)$ 값은 다음과 같다.

그래프에서 볼 수 있듯이, $\backslash varphi(n)$ 값은 대체로 $n$이 커짐에 따라 증가하는 경향을 보인다. 그래프의 가장 위쪽 점들을 잇는 선은 $y\; =\; n\; -\; 1$에 가까운데, 이는 $\backslash varphi(n)$의 상한이다. 이 상한은 $n$이 소수일 때만 정확히 도달한다. 반면, 간단한 하한으로는 $\backslash varphi(n)\; \backslash ge\; \backslash sqrt\{n/2\}$가 있지만, 이는 실제 값보다 상당히 느슨한 편이다. 그래프의 하극한은 $\backslash frac\{n\}\{\backslash log\; \backslash log\; n\}$에 비례하는 것으로 알려져 있다.^[30]

하디와 라이트는 $\backslash varphi(n)$의 크기가 "항상 '거의 $n$'"이라고 표현했다.^[27] 이는 다음 극한값으로 설명될 수 있다.

먼저,^[28]

:$\backslash lim\backslash sup\; \backslash frac\{\backslash varphi(n)\}\{n\}=\; 1$

하지만, $n$이 무한대로 갈 때,^[29] 모든 $\backslash delta\; >\; 0$에 대해

:$\backslash frac\{\backslash varphi(n)\}\{n^\{1-\backslash delta\}\}\backslash rightarrow\backslash infty$

이 두 공식은 $\backslash varphi(n)$에 대한 공식과 약수 함수 $\backslash sigma(n)$를 이용하여 증명할 수 있다. 특히 두 번째 공식을 증명하는 과정에서 $n\; >\; 1$에 대해 다음 부등식이 성립함이 밝혀진다.

:

또한 다음이 성립한다.^[30]

:$\backslash lim\backslash inf\backslash frac\{\backslash varphi(n)\}\{n\}\backslash log\backslash log\; n\; =\; e^\{-\backslash gamma\}$

여기서 $\backslash gamma$는 오일러-마스케로니 상수 ($\backslash gamma\; \backslash approx\; 0.577215665...$)이며, $e^\backslash gamma\; \backslash approx\; 1.7810724...$, $e^\{-\backslash gamma\}\; \backslash approx\; 0.56145948...$이다.

이 공식은 $\backslash log\; \backslash log\; n$이 무한대로 발산하므로 다음을 의미한다.

:$\backslash lim\backslash inf\backslash frac\{\backslash varphi(n)\}\{n\}=\; 0$

이 결과를 증명하는 데 소수 정리가 반드시 필요한 것은 아니다.^[31][32] 실제로 더 강한 결과가 알려져 있다.^[33][34][35]

:$\backslash varphi(n)\; >\; \backslash frac\; \{n\}\; \{e^\backslash gamma\backslash ;\; \backslash log\; \backslash log\; n\; +\; \backslash frac\; \{3\}\; \{\backslash log\; \backslash log\; n\}\}\; \backslash quad\backslash text\{for\; \}\; n>2$

그리고 무한히 많은 $n$에 대해

:

이 성립한다. 두 번째 부등식은 장루이 니콜라가 리만 가설이 참인 경우와 거짓인 경우를 나누어 증명했다.^[35]

$\backslash varphi(n)$의 평균적인 크기에 대해서는 다음 결과가 알려져 있다.^[21][36]

:$\backslash sum\_\{k=1\}^n\; \backslash varphi(k)\; =\; \backslash frac\{3n^2\}\{\backslash pi^2\}+O\backslash left(n(\backslash log\; n)^\backslash frac23(\backslash log\backslash log\; n)^\backslash frac43\backslash right)\; \backslash quad\backslash text\{as\; \}n\backslash rightarrow\backslash infty$

이는 아르놀트 발피쉬가 비노그라도프와 N. M. 코로보프의 지수 합 추정치를 이용하여 얻은 결과이다. 오차항은 H.-Q. Liu에 의해

:$$

O\left(n(\log n)^\frac23(\log\log n)^\frac13\right)



으로 개선되었다. 여기서 빅 $O$는 괄호 안의 함수에 상수배를 한 값 이하의 오차를 의미한다. 이 결과는 두 개의 무작위로 선택된 정수가 서로소일 확률이 $\backslash frac\{6\}\{\backslash pi^2\}$임을 보이는 데 사용될 수 있다.^[37]

5. 오일러의 정리

만약 양의 정수 $a,\; n$이 서로소라면, 다음과 같은 합동식이 성립한다. 이를 '''오일러의 정리'''라고 한다.

:$a^\{\backslash phi(n)\}\backslash equiv\; 1\backslash pmod\; n$

여기서 $\backslash phi(n)$은 오일러 피 함수이다. 이 정리는 $n$이 소수일 때의 특수한 경우인 페르마의 소정리를 일반화한 것이다. 페르마의 소정리는 소수 $p$와 $p$로 나누어지지 않는 정수 $a$에 대해 $a^\{p-1\}\; \backslash equiv\; 1\; \backslash pmod\; p$가 성립한다는 내용인데, 소수 $p$에 대해 $\backslash phi(p)=p-1$이므로 오일러 정리의 특수한 경우임을 알 수 있다.

오일러의 정리는 라그랑주의 정리를 정수 모듈러 n의 곱셈군 $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^\backslash times$에 적용하여 유도할 수 있다. 이 곱셈군의 위수는 $\backslash phi(n)$이므로, 군의 모든 원소 $a$에 대해 $a$의 위수는 $\backslash phi(n)$을 나누고, 따라서 $a^\{\backslash phi(n)\}\backslash equiv\; 1\backslash pmod\; n$이 성립한다.

RSA 암호 시스템은 오일러의 정리를 기반으로 한다. RSA에서 메시지 $m$을 암호화할 때는 공개된 키 $(n,\; e)$를 사용하여 $c\; \backslash equiv\; m^e\; \backslash pmod\; n$으로 암호문 $c$를 만든다. 암호문 $c$를 복호화할 때는 비밀 키 $d$를 사용하여 $m\; \backslash equiv\; c^d\; \backslash pmod\; n$으로 원래 메시지 $m$을 얻는다. 이때 비밀 키 $d$는 $ed\; \backslash equiv\; 1\; \backslash pmod\{\backslash phi(n)\}$을 만족하도록, 즉 $\backslash phi(n)$을 모듈로 하는 $e$의 곱셈 역원으로 선택된다.

오일러의 정리에 의해, $ed\; =\; k\backslash phi(n)\; +\; 1$ (k는 정수) 형태이므로

:$c^d\; \backslash equiv\; (m^e)^d\; \backslash equiv\; m^\{ed\}\; \backslash equiv\; m^\{k\backslash phi(n)+1\}\; \backslash equiv\; (m^\{\backslash phi(n)\})^k\; \backslash cdot\; m\; \backslash equiv\; 1^k\; \backslash cdot\; m\; \backslash equiv\; m\; \backslash pmod\; n$

이 성립하여 복호화가 가능하다.

RSA 암호의 안전성은 큰 수 $n$을 소인수분해하기 어렵다는 점에 기반한다. $n$이 두 개의 큰 소수 $p,\; q$의 곱($n=pq$)으로 만들어질 때, $\backslash phi(n)\; =\; (p-1)(q-1)$이 된다. $p$와 $q$를 알면 $\backslash phi(n)$을 쉽게 계산하여 비밀 키 $d$를 구할 수 있지만, $n$만 아는 상태에서는 $p,\; q$를 알아내기 어렵기 때문에($\backslash phi(n)$ 계산 및 $d$ 계산이 어려움), 암호 시스템의 안전성이 보장된다. 큰 수의 소인수분해는 현재까지 알려진 효율적인 알고리즘이 없어 계산적으로 매우 어려운 문제로 여겨진다.

6. 응용

오일러 피 함수($\backslash phi$)는 정수론의 기본적인 함수이지만, 그 응용 범위는 매우 넓어 추상대수학, 기하학, 암호학 등 다양한 수학 분야에 걸쳐 나타난다.

주요 응용 분야는 다음과 같다.

• 순환군: 군론에서 순환군의 생성원 개수를 세거나 특정 위수를 갖는 원소의 개수를 파악하는 데 사용된다.
• 정다각형 작도: 특정 정다각형이 자와 컴퍼스만으로 작도 가능한지 여부를 판별하는 데 중요한 기준을 제공한다. 이는 $\backslash phi(n)$ 값이 2의 거듭제곱인지와 관련된다.
• RSA 암호: 현대 암호학에서 널리 쓰이는 공개 키 암호 방식인 RSA 암호의 핵심 원리에 사용된다. 오일러 정리를 기반으로 암호화 및 복호화 과정이 설계되며, 오일러 피 함수 값의 계산 어려움이 암호 시스템의 보안성을 뒷받침한다.
• 기타 응용: 등차수열의 소수 정리와 같이 소수의 분포를 다루는 문제에도 활용된다.

6. 1. 순환군

6. 2. 정다각형 작도

6. 3. RSA 암호

6. 4. 기타 응용

7. 미해결 문제

'''토티언트 수'''는 오일러 피 함수의 값, 즉 $\backslash varphi(n)\; =\; m$을 만족하는 $n$이 적어도 하나 존재하는 $m$을 의미한다. 토티언트 수 $m$의 '''원자가''' 또는 '''중복도'''는 이 방정식의 해의 개수이다.^[40] ''비토티언트''는 토티언트 수가 아닌 자연수이다. 1을 초과하는 모든 홀수는 자명하게 비토티언트이다. 또한 무한히 많은 짝수 비토티언트가 있으며,^[41] 실제로 모든 양의 정수는 짝수 비토티언트인 배수를 갖는다.^[42]

7. 1. 레머의 추측

7. 2. 카마이클의 추측

7. 3. 리만 가설

참조

_[1] 웹사이트 Euler's totient function https://www.khanacad[...] 2016-02-26
_[2] 간행물
_[3] 간행물
_[4] 간행물
_[5] 간행물
_[6] 문서 Euler's theorem
_[7] 논문 Theoremata arithmetica nova methodo demonstrata Ferdinand Rudio
_[8] 문서
_[9] 문서
_[10] 논문 Speculationes circa quasdam insignes proprietates numerorum
_[11] 문서 phi
_[12] 문서 Disquisitiones Arithmeticae
_[13] 서적 A History Of Mathematical Notations Volume II Open Court Publishing Company
_[14] 논문 On certain ternary cubic-form equations
_[15] 문서 totient
_[16] 간행물
_[17] 문서 DA
_[18] 문서 DA
_[19] 문서
_[20] 문서 prop. 1
_[21] 서적 Weylsche Exponentialsummen in der neueren Zahlentheorie VEB Deutscher Verlag der Wissenschaften
_[22] 간행물 The scientific work of Arnold Walfisz http://matwbn.icm.ed[...]
_[23] 논문 On an error term of Landau II 1985
_[24] 간행물 Two problems on the distribution of Carmichael's lambda function
_[25] 간행물
_[26] 간행물
_[27] 간행물
_[28] 간행물
_[29] 간행물
_[30] 간행물
_[31] 문서
_[32] 간행물
_[33] 논문 Approximate formulas for some functions of prime numbers http://projecteuclid[...] 1962
_[34] 문서 thm. 8.8.7
_[35] 서적 The Book of Prime Number Records Springer-Verlag 1989
_[36] 서적 2006
_[37] 서적 1979
_[38] 서적
_[39] 서적 2006
_[40] 서적 2004
_[41] 서적 2004
_[42] 논문 On nontotients 1993
_[43] 논문 The distribution of totients 1998
_[44] 서적 2006
_[45] 서적 2006
_[46] 서적 2004
_[47] 서적 2004
_[48] 서적 2004
_[49] 간행물 The 7th § is arts. 336–366 DA
_[50] 문서 Gauss proved if {{mvar|n}} satisfies certain conditions then the {{mvar|n}}-gon can be constructed. In 1837 [[Pierre Wantzel]] proved the converse, if the {{mvar|n}}-gon is constructible, then {{mvar|n}} must satisfy Gauss's conditions
_[51] 간행물 art 366 DA
_[52] 간행물 art. 366. This list is the last sentence in the ''Disquisitiones'' DA
_[53] 서적
_[54] 논문 On the number of prime factors of {{mvar|n}} if {{math|''φ''(''n'')}} divides {{math|''n'' − 1}} 1980
_[55] 논문 On the equation {{math|''M''·φ(''n'') {{=}} ''n'' − 1}} 1988
_[56] 서적 2004
_[57] 서적 Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents Cambridge University Press 2017
_[58] 서적 The Words of Mathematics: An Etymological Dictionary of Mathematical Terms Used in English https://books.google[...] Mathematical Association of America 1994
_[59] OEIS A000010
_[60] 서적 Additive Number Theory: The Classic Bases Springer 1996
_[61] 웹사이트 Is the Euler phi function bounded below? https://math.stackex[...] 2020-03-26