오일러 피함수 \(Euler's phi function\)

오일러 피함수는 양의 정수 $n$에 대하여 $n$보다 작은 양의 정수 $m$에 대해

 

$gcd(n,m)=1$인 $m$의 개수를 세는 함수이다.

 

오일러 피함수는 다음과 같이 정의되기도 한다.

 

$\varphi (n)=|\{m|1\leq m\leq n,gcd(n,m)=1\}|$

 

오일러 피함수는 특별한 성질을 가지고 있는데

 

바로 곱셈적 함수라는 것이다.

 

$gcd(a,b)=1$ 인 $a,b$에 대해

 

$\varphi (ab)=\varphi (a)\varphi (b)$가 성립한다는 것이다.

 

증명은 다음 자료를 참고했다. 

 

https://blog.chodaeho.com/posts/2021/eulers-totient-function/

오일러 피 함수(Euler's phi (totient) function)

 

각 행은 공차가 $a$이고 길이가 $b$ 등차수열로, 각 열은 공차가 $1$인 등차수열인 $ab$ 테이블을 보자

 

$1\;\;a+1\;\;2a+1\;\;3a+1\;\;...\;\;(b-1)a+1$

$2\;\;a+2\;\;2a+2\;\;3a+2\;\;...\;\;(b-1)a+2$

$...$

$a\;\;2a\;\;3a\;\;...\;\;ab$

 

이 수들은 1부터 $ab$까지 연속적인 수들이다.

 

먼저 $r$번째 행에 있는 수들은 $ka+r(0\leq k\leq (b-1))$로 표현될 수 있고, 이들의 $\mod a$ 값은 모두

 

$r$로 동일하다. $r=1$ 이면 $a$와 서로소이고, $b$도 $a$와 서로소 이기 때문에 $b$와도 서로소 이다.

 

이때 $gcd(a,ka+r)=1$ 인 행들은 $\varphi (a)$개가 있음을 알고 있다.

 

이제 각 행에 대하여 $ab$와 서로소인 수 개수가 $\varphi (b)$ 개가 있음을 알면 된다. 

 

먼저 $ka\mod b$는 순환성을 가지고, 그것에 $+r\mod b$는 $mod$ 값을 좌우로

 

평행이동시켜주는 기능만을 하므로 $ka+r\mod b$는 순환성을 가진다. \(증명은 맨 아래에 두었다.\)

 

따라서 $r$ 행에 있는 $n$개의 $gcd(b,ka+r)={0,1,2,...b-1}$로 unique하다.

 

unique한 $gcd(b,ka+r)$ 값을 가지는 $ka+r$ 들 중에서 $b$와 서로소인 수의 개수는

 

$\varphi (b)$ 와 같으므로 $\varphi (ab)=\varphi (a)\varphi (b)$이다.

 

$ka\mod b$의 unique 증명 

 

$k=0,1,2,3...b-1$ 인 $k$에 대해

 

만약 $k_1a\equiv k_2a$가 있다고 가정하면

 

모듈러 연산 규칙에 의해 (\양변에서 같은 값을 빼줌\)

 

$a(k_1-k_2)\equiv 0$ 이므로 $(k_1-k_2)|b$이다.

 

그런데 $|k_1-k_2|<b$ 이므로 $k_1=k_2$이다.

 

따라서 $k_1a\equiv k_2a$ 인 경우는 $k_1=k_2$ 인 경우 밖에 없고

 

$ka\mod b$는 unique하다.