7. 정수론: 오일러의 피 함수과 페르마의 소정리 (Number Theory: Euler's Phi Function and Fermat's Little Theorem)

오일러의 피 함수^{Euler's Totient(phi) Function}

오일러의 피 함수 $\phi(n)$는 어떤 양의 정수 $n$에 대해, $0$부터 $n$까지의 정수 중 $n$과 서로소인 정수의 갯수를 나타내는 함수이다.

예를들어, $\phi(6)$은 $0~6$중 $1, 5$만이 $6$과 서로소이므로 2이다.

오일러의 정리^{Euler's Theorem}

만약 $\text{gcd}(n,k)=1$이면, ($n,k$가 서로소이면) $k^{\phi (n)} \equiv 1 (\mod n)$이다.

예를들어, 4와 9가 서로소이므로, $4^{\phi (9)} = 4^6 = 4096\equiv 1 (\mod 9)$이다.

만약 $n,k$가 서로소이면, $k$는 $(\mod n)$에 대한 $k^{-1}$을 갖는다.

$n$ 이하의 자연수 중, $n$과 서로소인 자연수들의 집합을 $S$라 하자.

$S$의 원소의 갯수는 $\phi(n)$이다.

$S = \{s_0, s_1, \cdots s_n\}$이라 하자.

$n$과 서로소인 어떤 수 $a$를 $S$에 곱하면

$aS = \{as_0, as_1, \cdots as_n\}$

이때, $n$에 대해 서로소인 두 수의 곱은 역시 $n$과 서로소이므로, $aS$의 모든 원소는 $n$과 서로소이다.

또한, $aS$의 원소들을 $n$으로 나눈 나머지는 $S$의 원소들의 재배열이 되므로, $S$의 모든 원소의 곱과 $aS$의 모든 원소의 곱은 $n$으로 나눈 나머지가 같다.

$$b_1\cdots b_{\phi(n)} \equiv a^{\phi(n)}b_1 \cdots b_{\phi(n)} (\mod n)$$

$$a^{\phi (n)} \equiv 1(\mod n)$$

예제

$n=6$면, $S=\{1,5\}$다.

$a=5$로 놓으면 $aS = \{5, 25\}$이므로,

$$ 1\cdot 5 \equiv 5^2 \cdot 5\cdot 25 (\mod 6)$$

페르마의 소정리^{Fermat's Little Theorem}

페르마의 소정리는 오일러의 정리의 따름 정리이다.

소수 $p$와 서로소인 임의의 정수 $a$에 대해, 

$$ a^{p-1} \equiv 1 (\mod p)$$

가 성립한다는 것이다.

예를들어, $p=7, a=8$로 놓고 보면, $8^6 \equiv 1 (\mod 7)$이다.

페르마의 소정리는 오일러의 정리에 $n$ 자리에 $p$를 대입하여 증명할 수 있다.

$k^{\phi(p)} \equiv 1 (\mod p)$인데, 이때, $\phi(p)$는 소수이므로 $p-1$이 된다.

$k^{p-1} \equiv 1 (\mod p)$로 바로 증명이 되었다.