정수론 (6) - 오일러의 정리와 오일러 파이 함수
저번에는 페르마 소정리에 대해서 알아보았습니다.
$$
a^{p-1} \equiv 1 \mod p \quad \text{(단, $a$와 $p$는 서로소)}
$$
이번엔 페르마 소정리의 일반화 버전인 오일러 정리를 보도록 하겠습니다. 오일러 정리는 아래와 같습니다.
$$
a^{\varphi(n)} \equiv 1 \mod n \quad \text{(단, $a$와 $n$은 서로소)}
$$
여기서 $\varphi(n)$ 은 오일러 파이 함수 (Euler Phi Function) 으로 불리는 함수로, 1부터 $n$ 까지 $n$ 과 서로소인 수들의 개수입니다. 예를 들어서 $\varphi (10)$ 을 구하면, 10과 서로소인 수는 1, 3, 7, 9이므로, $\varphi(10) = 4$ 입니다.
눈치 좋은 분들은 알아채셨겠지만, 페르마 소정리는 오일러 정리에서 $n$ 이 소수인 특수한 경우입니다. $p$ 가 소수라면 $\varphi (p) = p-1$ 이 되므로, 오일러 정리에 따라서 $a^{p-1} \equiv 1 \mod p$ 가 됩니다.
오일러 정리의 증명
오일러 정리와 페르마 소정리의 내용이 상당히 유사하듯, 증명도 상당히 유사합니다. 저번 시간에 얘기했던 기약잉여계를 이용하면 됩니다.
기약잉여계: $n$ 과 서로소인 $n$ 이하의 정수로 이루어진 집합 $M$ 을 기약잉여계라고 한다.
정수 $n$의 기약잉여계 $M$ 의 모든 원소를 다음과 같이 써 보겠습니다.
$$
M = \lbrace p_1, p_2, \cdots, p_{\phi(n)} \rbrace
$$
여기에서 $\varphi(n)$ 은 아까 전에 소개해드린 오일러 파이 함수입니다. 저번 글 페르마의 소정리와 동일한 단계를 밟으면 $a, n$이 서로소일 때 위 집합은 아래의 집합과 동일한 집합임을 보일 수 있습니다.
$$
aM = \lbrace ap_1, ap_2, \cdots, ap_{\varphi (n)} \rbrace
$$
여기서 $M$ 과 $aM$ 의 각 원소를 곱한 값이 같아야 합니다.
$$
\begin{align}
p_1p_2\cdots p_{\varphi (n)} &\equiv (ap_1)(ap_2)\cdots(ap_{\varphi(n)})
\end{align}
$$
여기서 기약잉여계가 활약합니다. 기약잉여계는 $n$과 서로소인 수들로만 이루어져 있으므로, 기약잉여계의 원소의 총 곱인 $p_1p_2 \cdots p_{\varphi(n)}$도 $n$과 서로소입니다. 따라서 양변을 $p_1p_2 \cdots p_{\varphi(n)}$로 나눌 수 있으며, 그 결과가 오일러 정리입니다. $$ \therefore a^{\varphi(n)} \equiv 1 \mod n $$
오일러 파이 함수는 곱셈적 함수이다
생각보다 엄청 쉬웠죠? 사실 이번 글의 메인 주제는 오일러 정리의 증명이 아니라, 오일러 파이 함수를 어떻게 계산할 수 있느냐입니다. 오일러 정리를 알고는 있어도, 오일러 파이 함수를 계산할 수 있어야지 실제로 정리를 써먹을 수 있으니까요. 오일러 파이 함수의 계산을 위한 가장 중요한 성질은 오일러 파이 함수가 곱셈적 함수 라는 성질입니다. 이는 다음을 의미합니다.
$$
\varphi(m)\varphi(n) = \varphi(mn) \quad \text{(단, $m, n$은 서로소)}
$$
이 사실의 증명은 조금 더 복잡합니다. 먼저 다음과 같은 $m \times n$ 의 표를 보겠습니다.
$$
\begin{matrix}
1 & m+1 & 2m+1 & & (n-1)m+1 \\
2 & m+2 & 2m+2 & \cdots & (n-1)m+2 \\
3 & m+3 & 2m+3 & & (n-1)m+3 \\
& \vdots & & \ddots & \vdots\\
m & 2m & 3m & \cdots & nm
\end{matrix}
$$
이 표에서 $r$ 행은 다음과 같이 생겼습니다.
$$
\begin{matrix}
r & m+r & 2m+r & \cdots & (n-1)m+r
\end{matrix}
$$
여기서 다음 두 가지 경우를 생각해 보겠습니다.
- $r$은 $m$ 과 서로소가 아니다: $r$ 행, 즉 $km+r$ 꼴의 모든 수는 $m$ 과 서로소가 아닙니다.
- $r$은 $m$ 과 서로소이다: $r$ 행, 즉 $km+r$ 꼴의 모든 수는 $m$ 과 서로소입니다.
우리는 두 번째 케이스에만 집중할 것입니다. 두 번째 케이스의 경우, $r$행의 $n$개의 수들은 법 $n$에 대해 서로 다릅니다. 이는 귀류법으로 보일 수 있습니다. 만약 $im + r \equiv jm + r \mod n$ 이라면, $im \equiv jm \mod n$ 이 되고, $m, n$ 이 서로소이므로 양변을 $m$으로 나눌 수 있어 $i \equiv j \mod n$ 이 됩니다. 그런데 $i, j < n$ 이므로 $i = j$ 가 되어 모순입니다. 즉, 우리는 다음 사실을 알아냈습니다.
$r$이 $m$과 서로소일 때, $r$행의 원소들은 법 $n$에 대해 서로 다르다.
그런데 $r$행의 원소가 $n$개 존재하므로, $r$행은 다음 집합과 합동입니다.
$$
\lbrace r, m+r, 2m+r, \cdots, (n-1)m+r \rbrace \equiv \lbrace 0, 1, 2, \cdots, n-1\rbrace \mod n
$$
0부터 $n-1$ 까지 모든 수가 빠짐없이 있으므로, 여기에는 $n$ 과 서로수인 $\varphi (n)$ 개의 수들도 빠짐없이 있을 것입니다. 그런데 애초에 $r$행은 모두 $m$과 서로소이므로, $r$행의 수 중 $n$과 서로소인 수는 $mn$과 서로소입니다. 한편 이런 행은 $\varphi(m)$개 존재합니다. 따라서, $mn$과 서로소인 수들의 총 개수는 $\varphi(m)\varphi(n)$이 됩니다!
정리하면 다음과 같습니다.
- $m \times n$ 의 표로 수를 쭉 쓰면, $m$과 서로소인 정수 $r$에 대해 $r$행의 수들은 모두 $m$과 서로소이며, 법 $n$에 대해 서로 다르다.
- 그런데 $r$행에는 $n$개의 수가 있으므로, 이는 0부터 $n-1$까지 모든 수가 빠짐없이 있다는 말이며, $n$과 서로소인 $\varphi(n)$개의 수들도 빠짐없이 있다는 말이다.
- 한편 $r$행의 모든 수는 $m$과 서로소이므로, 이 수들은 $m, n$과 동시에 서로소이며, 즉 $mn$과 서로소이다.
- 이러한 $r$은 $\varphi(m)$개 있으므로, $mn$과 서로소인 수들은 총 $\varphi(m)\varphi(n)$개가 있다.
오일러 파이 함수의 계산
먼저 $p$가 소수일 때 $\varphi(p^k)$의 계산법을 알아봅시다. $p$가 소수라면, $p^k$와 서로소가 아닌 수들은 반드시 $p$를 인수로 가져야 합니다. 1부터 $p^k$까지의 수 중 이런 수들은 $p^k / p = p^{k-1}$개가 있습니다. 따라서 다음 결론을 얻습니다.
$$
\varphi(p^k) = p^k - p^{k-1}
$$
이 결론으로부터 우리는 쉽게 오일러 파이 함수를 계산할 수 있습니다. 모든 수는 소수의 곱으로 나타낼 수 있으므로, 소인수분해를 한 뒤 오일러 파이 함수가 곱셈적 함수임을 이용해서 계산하면 됩니다. 공식으로 깔끔히 정리하면 아래와 같습니다. $a = p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$에 대하여
$$
\begin{align}
\varphi(a) &= \varphi(p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}) \\
&= \varphi(p_1^{k_1})\varphi(p_2^{k_2})\cdots \varphi(p_n^{k_n}) \\
&= p_1^{k_1}\left( 1-\frac{1}{p_1} \right)p_1^{k_2}\left( 1-\frac{1}{p_2} \right)\cdots p_1^{k_n}\left( 1-\frac{1}{p_n} \right) \\
&= p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}\left( 1-\frac{1}{p_1} \right)\left( 1-\frac{1}{p_2} \right)\cdots\left( 1-\frac{1}{p_n} \right) \\
&= a\left( 1-\frac{1}{p_1} \right)\left( 1-\frac{1}{p_2} \right)\cdots\left( 1-\frac{1}{p_n} \right)
\end{align}
$$
이렇게 오일러 정리와, 오일러 파이 함수를 계산하는 방법에 대해서 알아보았습니다. 다음 번에는 약간 번외편으로 오일러 정리가 어떻게 암호학에 쓰일 수 있는지 알아보도록 하겠습니다 :)
