오일러 피 함수

Euler's phi function, Euler's totient function

정수론에서

정수론에서 [math]\displaystyle{ \phi\left(n\right) }[/math]은 [math]\displaystyle{ n }[/math]보다 작거나 같은 양의 정수 중에서 [math]\displaystyle{ n }[/math]과 서로소인 수의 개수를 나타내는 함수다. 예를 들면, 6보다 작거나 같은 수 중에 6과 서로소인 수는 1, 5의 두 개 뿐이므로 [math]\displaystyle{ \phi\left(6\right)=2 }[/math]가 된다.

성질

1. 임의의 양의 정수 [math]\displaystyle{ n }[/math]의 기약잉여계의 원소의 수는 [math]\displaystyle{ \phi\left(n\right) }[/math]이다.
2. [math]\displaystyle{ \gcd\left(a,n\right)=1 }[/math]인 정수 [math]\displaystyle{ a }[/math]에 대해 [math]\displaystyle{ a^{\phi\left(n\right)}\equiv1\pmod n }[/math]이 성립한다.
3. [math]\displaystyle{ p }[/math]가 소수면, [math]\displaystyle{ \phi\left(p\right)=p-1 }[/math]이다. 역도 성립한다.
4. 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ \phi\left(p^a\right)=p^a-p^{a-1} }[/math]이다.
5. 오일러 피 함수는 곱셈적 함수이다. 즉, 서로소인 양의 정수 [math]\displaystyle{ m,\,n }[/math]에 대해 [math]\displaystyle{ \phi\left(mn\right)=\phi\left(m\right)\phi\left(n\right) }[/math]가 성립한다.
6. [math]\displaystyle{ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} }[/math]라 하자 (단, [math]\displaystyle{ p_i }[/math]는 서로 다른 소수, [math]\displaystyle{ a_i }[/math]는 자연수). 그럼 [math]\displaystyle{ \phi\left(n\right)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right) }[/math]이다.
7. [math]\displaystyle{ n\gt 2 }[/math]이면 [math]\displaystyle{ \phi\left(n\right) }[/math]는 짝수다.
8. [math]\displaystyle{ m\mid n }[/math]이면 [math]\displaystyle{ \phi\left(m\right)\mid\phi\left(n\right) }[/math]이다.
9. [math]\displaystyle{ \phi\left(n^k\right)=n^{k-1}\phi\left(n\right) }[/math]
10. [math]\displaystyle{ \sum_{d\mid n}\phi\left(d\right)=n }[/math]

증명

1. 기약잉여계의 정의에 의해 자명하다.
2. 오일러의 정리 참조.
3. 쉬우므로 생략. 증명은 독자에게 연습문제로 남긴다.
4. [math]\displaystyle{ p^a }[/math]와 서로소가 아닌 수는 [math]\displaystyle{ p }[/math]를 반드시 약수로 가져야 한다. 이는 곧 [math]\displaystyle{ p }[/math]의 배수를 의미하고, [math]\displaystyle{ p^a }[/math]보다 작거나 같은 [math]\displaystyle{ p }[/math]의 배수는 [math]\displaystyle{ p^a\div p=p^{a-1} }[/math]이다. [math]\displaystyle{ \therefore\phi\left(p^a\right)=p^a-p^{a-1} }[/math]
5. 1부터 [math]\displaystyle{ mn }[/math]까지의 정수를 다음과 같이 나타내자.

1	m+1	2m+1	…	(n-1)m+1
2	m+2	2m+2	…	(n-1)m+2
[math]\displaystyle{ \vdots }[/math]	[math]\displaystyle{ \vdots }[/math]	[math]\displaystyle{ \vdots }[/math]		[math]\displaystyle{ \vdots }[/math]
r	m+r	2m+r	…	(n-1)m+r
[math]\displaystyle{ \vdots }[/math]	[math]\displaystyle{ \vdots }[/math]	[math]\displaystyle{ \vdots }[/math]		[math]\displaystyle{ \vdots }[/math]
m	2m	3m	…	mn

만약 [math]\displaystyle{ \gcd\left(r,m\right)=d\neq1 }[/math]이면, [math]\displaystyle{ d\mid r,\,d\mid m }[/math]이므로 [math]\displaystyle{ d\mid km+r }[/math]이다. 즉, [math]\displaystyle{ \gcd\left(km+r,mn\right)\geq d }[/math]. 따라서 [math]\displaystyle{ r }[/math]번째 줄은 [math]\displaystyle{ mn }[/math]과 서로소인 정수를 포함하고 있지 않다. 만약 [math]\displaystyle{ \gcd\left(r,m\right)=1 }[/math]이면, [math]\displaystyle{ r }[/math]번째 줄에는 [math]\displaystyle{ r,\,m+r,\,2m+r,\,\cdots,\,\left(n-1\right)m+r }[/math]를 포함하고 있고, 이 수들은 [math]\displaystyle{ m }[/math]과 서로소이다. 만약 서로소가 아니라면, [math]\displaystyle{ d\neq1 }[/math]인 [math]\displaystyle{ d }[/math]에 대해 [math]\displaystyle{ d\mid m,\,d\mid km+r }[/math]이므로 [math]\displaystyle{ d\mid r }[/math]이 되어 [math]\displaystyle{ d\mid\gcd\left(m,r\right)=1 }[/math]이 되어 모순이다. 또한, 이 수들은 법 [math]\displaystyle{ n }[/math]에 대해 서로 다르다. 만약 [math]\displaystyle{ im+r\equiv jm+r\pmod n }[/math]이라면 [math]\displaystyle{ im\equiv jm\pmod n }[/math]이고, [math]\displaystyle{ \gcd\left(m,n\right)=1 }[/math]이므로 [math]\displaystyle{ i\equiv j\pmod n }[/math]이다. 그런데 [math]\displaystyle{ 0\leq i,\,j\leq n-1 }[/math]이므로 [math]\displaystyle{ i=j }[/math]여야만 한다. 정리하면, 저 수들은 법 [math]\displaystyle{ n }[/math]에 대해 기약잉여계를 구성한다. 1번 성질에 의해, 저 수들 중에 [math]\displaystyle{ n }[/math]과 서로소인 수의 개수는 [math]\displaystyle{ \phi\left(n\right) }[/math]이다. 한편, 저런 수들의 집합은 [math]\displaystyle{ \phi\left(m\right) }[/math]개 존재한다.
[math]\displaystyle{ \therefore\phi\left(mn\right)=\phi\left(m\right)\phi\left(n\right) }[/math].

6.
[math]\displaystyle{ \begin{align*}\phi\left(n\right)&=\phi\left(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\right)\\&=\phi\left(p_1^{a_1}\right)\phi\left(p_2^{a_2}\right)\cdots\phi\left(p_k^{a_k}\right)\\&=\left(p_1^{a_1}-p_1^{a_1-1}\right)\left(p_2^{a_2}-p_2^{a_2-1}\right)\cdots\left(p_k^{a_k}-p_k^{a_k-1}\right)\\&=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)\\&=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)\end{align*} }[/math]

7. 6번 성질에서 [math]\displaystyle{ \phi\left(n\right)=\prod_{i=1}^{k}\left(p_i^{a_i}-p_i^{a_i-1}\right)=\prod_{i=1}^{k}p_i^{a_i-1}\left(p_i-1\right) }[/math]임을 알 수 있다. 그런데 [math]\displaystyle{ n\gt 2 }[/math]이므로, [math]\displaystyle{ n }[/math]은 홀수인 소인수를 가지거나 소인수 2를 두 번 이상 가진다. 곧, 위 공식에서 [math]\displaystyle{ \phi\left(n\right) }[/math]가 짝수임을 유도할 수 있다.

8. [math]\displaystyle{ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} }[/math] ([math]\displaystyle{ a_i }[/math]는 자연수)라 하면, [math]\displaystyle{ m\mid n }[/math]이므로 [math]\displaystyle{ m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} }[/math] ([math]\displaystyle{ a_i }[/math]는 음이 아닌 정수)가 된다. 6번 성질에서 [math]\displaystyle{ \phi\left(m\right)\mid\phi\left(n\right) }[/math]임이 바로 유도된다.

9. [math]\displaystyle{ n=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m} }[/math]라 하면, [math]\displaystyle{ n^k=p_1^{ka_1}p_2^{ka_2}\cdots p_m^{ka_m} }[/math]이다. 6번 성질을 적용하면 [math]\displaystyle{ \phi\left(n^k\right)=n^{k-1}\phi\left(n\right) }[/math]임이 바로 유도된다.

10. 1부터 [math]\displaystyle{ n }[/math]까지의 수를 다음과 같은 규칙에 의해 분류한다.

[math]\displaystyle{ \gcd\left(m,n\right)=d }[/math]이면 [math]\displaystyle{ m\in C_d }[/math]

그러면, [math]\displaystyle{ m\in C_d }[/math]이기 위한 필요충분 조건은 [math]\displaystyle{ \gcd\left(m/d,n/d\right)=1 }[/math]임을 알 수 있다. 곧, [math]\displaystyle{ \left|C_d\right|=\phi\left(n/d\right) }[/math]이다. 또한, [math]\displaystyle{ C_d }[/math]는 [math]\displaystyle{ n }[/math]의 partition임을 알 수 있다. 따라서, [math]\displaystyle{ n=\sum_{d\mid n}\phi\left(n/d\right) }[/math]. 그런데 모든 약수 [math]\displaystyle{ d }[/math]에 대해 값을 더하므로, [math]\displaystyle{ \sum_{d\mid n}\phi\left(n/d\right)=\sum_{d\mid n}\phi\left(d\right) }[/math].
[math]\displaystyle{ \therefore n=\sum_{d\mid n}\phi\left(d\right) }[/math]