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

오일러 피(파이) 함수 $\varphi (n)$는 $1$부터 $n$까지 정수 중 $n$과 서로소인 수의 개수를 세는 함수이다.

공식

양의 정수 $n$에 대해 오일러 피 함수는 다음과 같이 정의된다.

$$\varphi (n)=\prod p_i^{a_i-1}(p_i-1)$$

이때 각 $p_i$는 $n$의 소인수이고 $a_i$는 $p_i$의 차수이다. 즉 $n$을 소인수분해 하면 $\prod p_i^{a_i}$이다.

증명

Lemma 1. $n$이 소수 $p$에 대해 $n=p^k$인 경우 $\varphi (n)=p^{k-1}(p-1)$이다.

$1$ 이상 $p^k$ 이하 정수이면서 $p^k$와 서로소가 아니려면 소인수로 $p$를 가지면 된다. 따라서 $p$의 배수이면 되므로 이런 수는 $p,2p,3p\cdots p^{k-1}p$, 총 $p^{k-1}$개 이다. 그러므로 $n$이 소수 $p$의 $k$제곱수인 경우 오일러 피 함수는 다음과 같이 정의된다.

$$\therefore \varphi (n)=p^k-p^{k-1}=p^{k-1}(p-1)$$

Lemma 2. 오일러 피 함수는 곱셈적 함수(multiplicative function)이다.

$m$과 $n$이 서로소일 경우, $\varphi (mn)=\varphi (m)\varphi (n)$임을 보일것이다.

$m$과 $n$이 서로소라고 하자. 이때 $1$부터 $mn$까지 숫자를 나열하는 $m\ast n$ 테이블을 그리고, 이 테이블에서 $mn$과 서로소인 숫자가 몇 개인지 세면 그 값이 $\varphi (mn)$이다.

$$\begin{array}{ccccc}1& m+1& 2m+1& \cdots & (n-1)m+1\\ 2& m+2& 2m+2& \cdots & (n-1)m+2\\ 3& m+3& 2m+3& \cdots & (n-1)m+3\\ ⋮& ⋮& ⋮& & ⋮\\ m& 2m& 3m& \cdots & nm\end{array}$$

테이블에서 $r\text{th row}$의 값들은 $km+r$의 꼴이다($0\le k\le n-1$). 이때 $d=gcd(m,r)$라고 하자.

$d>1$인 경우 $gcd(m,r)=gcd(m,km+r)$이므로($\because$ 유클리드 호제법) $km+r$과 $mn$은 공약수 $d$를 가진다. 따라서 이 경우 $r\text{-th row}$의 수들은 모두 $mn$과 서로소가 아니다.

반대로 $d=1$인 경우 같은 이유로 $km+r$는 $m$과 서로소이다. 따라서 이런 $\text{row}$에서 $n$과도 서로소인 수는 $mn$과 서로소이다. 그리고 그런 $\text{row}$는 $\varphi (m)$개 있음을 알고 있다. 이제 각 $\text{row}$마다 $n$과 서로소인 수는 정확히 $\varphi (n)$개 있음을 보이면 된다.

$r\text{th row}$의 수들은 다음과 같은데, $r$에 $m$을 더하는 것을 $n-1$번 반복하는 꼴이다.

$$r,m+r,2m+r\cdots (n-1)m+r$$

$m$과 $n$이 서로소이므로, 이 수들을 $modn$하면 $0$부터 $n-1$까지의 수가 정확히 한 번씩 나오게 된다. (이빨의 개수가 서로소인 두 개의 톱니바퀴가 맞물려 돌아가는 것을 떠올려보라.)

$gcd(x+kn,n)=gcd(x,n)$이므로 $modn$한 값이 $n$과 서로소라면 원래 값도 $n$과 서로소이고, 그 이도 성립한다. $1$부터 $n(\equiv 0modn)$까지 정수 중 $n$과 서로소인 수는 $\varphi (n)$개 있으므로, 각 $\text{row}$마다 $n$과 서로소인 수는 정확히 $\varphi (n)$개 있다.

결론적으로 $1$부터 $mn$까지 숫자를 나열한 $m\ast n$ 테이블에서, $mn$과 서로소인 수가 포함된 $\text{row}$는 $\varphi (m)$개이고 해당 $\text{row}$마다 $mn$과 서로소인 수는 $\varphi (n)$개이다.

$$\therefore \varphi (mn)=\varphi (m)\varphi (n)$$

Theorem 1. 모든 양의 정수 $n$에 대해 $\varphi (n)=\prod p_i^{a_i-1}(p_i-1)$이다.

$n=1$인 경우는 자명하고, $1$보다 큰 양의 정수 $n$은 소수의 $k$제곱수들의 곱이므로, Lemma 1, 2의 결과에 따라 오일러 피 함수의 정당성을 증명하였다.

출처: Loyola University Chicago 수업자료