Number Theory - 7.3 오일러 정리

오일러 정리

Lemma

$n > 1$ 이고 $gcd(a,n)=1$ 이라 하자.

$a_1, a_2, \dots, a_{\phi(n)}$이 $n$이하의 $n$과 서로소인 양의 정수이면,

$\phi(n)$의 원소들

$$ aa_1, aa_2, \dots, aa_{\phi(n)} $$

은 법 $n$에 대해 어떤 순서로 $a_1, a_2, \dots, a_{\phi(n)}$과 합동이다.

증명

$aa_1, aa_2, \dots, aa_{\phi(n)}$의 어느 정수도 법 $n$에 대해 합동이 아니라면,

$$ \begin{aligned} aa_i &\equiv aa_j \pmod n\\ a_i &\equiv a_j \pmod n \end{aligned} $$

이 되기 때문에 모순이다.

$a_i \perp n$ 그리고, $a \perp n$ 이기 때문에 $aa_i \perp n$ 이다.

앞선 단원의 보조 정리를 참고한다.

어떤 $aa_i$에 대해 $aa_i \equiv b \pmod n$인 유일한 정수 $b~(0 \le b < n)$이 존재한다.

$$ gcd(b,n)=gcd(aa_i,n)=1 $$

그런데 $0 \le b < n$ 이고 $gcd(b,n)=1$ 이므로 $b$는 각각 $a_i$에 대응된다.

이것은 $aa_1, aa_2, \dots, aa_{\phi(n)}$과 그리고 $a_1, a_2, \dots, a_{\phi(n)}$이 법 $n$에 대해 어떤 순서로 같다는 것을 보인다. $\square$

Theorem 7.5 오일러 정리 ⭐️

$n \ge 1$이고 $gcd(a,n)=1$ 이면

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

증명 1

$n > 1$을 택해도 무방하다.

$a_1, a_2, \dots, a_{\phi(n)}$이 $\phi(n)$의 집합이라고 하자.

$gcd(a,n)=1$ 이므로 보조정리로부터 $aa_1, aa_2, \dots, aa_{\phi(n)}$은 나타난 순서와 상관없이 $a_1, a_2, \dots, a_{\phi(n)}$과 합동이다.

$$ \begin{aligned} aa_1 &\equiv a'_1 \pmod n\\ aa_2 &\equiv a'_2 \pmod n\\ \vdots\\ aa_{\phi(n)} & \equiv a'_{\phi(n)} \pmod n \end{aligned} $$

이 $\phi(n)$개의 합동식을 모두 곱하면,

$$ a^{\phi(n)}(a_1a_2 \cdots a_{\phi(n)}) \equiv (a_1a_2 \cdots a_{\phi(n)}) \pmod n $$

$(a_1a_2 \cdots a_{\phi(n)}) \perp n$ 이므로 양변을 소거하면,

$$ a^{\phi(n)} \equiv 1 \pmod n ~~~~ \blacksquare $$

오일러 정리와 페르마 정리

$n$이 소수라면 $\phi(n)=n-1$ 이기 때문에

$$ a^{p-1} \equiv 1 \pmod p $$

오일러 정리가 페르마 정리의 일반화이다.

증명 2

귀납법을 사용하자.

$p \nmid a$ $(p \text{ 는 소수})$ 일 때 $a^{\phi(p^k)} \equiv 1 \pmod {p^{k}}$ 를 보자.

$k=1$ 일 때는 페르마 정리에 의해 성립한다.

고정된 $k$에 대해 위 식이 성립한다고 가정하자. 그럼 어떤 정수 $q$를 이용해

$$ a^{\phi(p^k)}-1 = q \cdot p^k $$

또한 다음을 보자.

$$ \phi(p^{k+1})=p^{k+1}-p^k=p \left( p^k-p^{k-1} \right)=p \cdot \phi(p^k) $$

이항 정리를 이용해 다음과 같이 전개한다.

$$ \begin{aligned} a^{\phi(p^{k+1})}&=a^{p \cdot \phi(p^k)}\\ &=\left( a^{\phi(p^k)} \right)^p=(1+q \cdot p^k)^p\\ &=\dbinom {p}{0}1+\dbinom {p}{1}(q \cdot p^k)+ \dbinom {p}{2}(q \cdot p^k)^2\\ &~~~~~~~~~~~~+\cdots+\dbinom {p}{p}(q \cdot p^k)^p\\ & \equiv 1 \pmod {p^{k+1}} \end{aligned} $$

${}_P\mathrm{ C} _0$ 말고는 모두 $p^{k+1}$ 로나누어 떨어지기 때문이다.

즉, 귀납식이 성립하게 된다.

이제 $p^k$ 에 대해서는 알아보았고, $n=p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}$이라 하자.

$$ a^{\phi \left( p_i^{k_i} \right)} \equiv 1 \pmod {p_i^{k_i}} $$

임을 보였으므로 합동식의 성질로 양변에 $\dfrac {\phi(n)}{\phi \left( p_i^{k_i} \right)}$ 거듭제곱을 한다면,

$$ \begin{aligned} a^{\phi(n)} &\equiv 1 \pmod {p_i^{k_i}}\\ &~~~~~~\Downarrow\\ p_i^{k_i}& \mid a^{\phi(n)}-1 \end{aligned} $$

모든 $p_i^{k_i}$는 서로소이므로 Theorem 2.4 Corollary에 의해 $n \mid a^{\phi(n)}-1$

결국,

$$ a^{\phi(n)} \equiv 1 \pmod n~~ \blacksquare $$

오일러 정리의 활용

중국인의 나머지 정리

모두 서로소인 $n_i$에 대해 $x \equiv a_i \pmod {n_i}$ 인 합동식이 있을 때,

법 $\prod_{i=1}^{r} n_i$ 에 대한 해 $x$가 유일히 존재한다.

증명

$N=\prod_{i=1}^r n_i,~~~~N_i=N/n_i$ 라 하자.

$x=\sum_{i=1}^r a_iN_i^{\phi(n_i)}$ 를 고려하자.

$n_i \mid N_j ~~(i \ne j)$ 이므로, $x \equiv a_iN_i^{\phi(n_i)} \pmod {n_i}$

$N_i \perp n_i$ 이므로 오일러 정리에 의해 $N_i^{\phi(n_i)} \equiv 1 \pmod {n_i}$

즉, $x \equiv a_i \pmod {n_i} ~~~~ \blacksquare$

$n$이 $5$의 배수가 아닌 홀수이면 $n$은 각 자리가 모두 $1$인 어떤 정수를 나눈다.

$gcd(n,10)=gcd(9,10)=1 ~ \Longrightarrow gcd(9n,10)=1$

$$ 10^{\phi(9n)} \equiv 1 \pmod {9n} $$

어떤 정수 $q$가 존재하여

$$ \begin{aligned} 10^{\phi(9n)}-1 &= q \cdot 9n\\ \dfrac {10^{\phi(9n)}-1}9 &= q \cdot n\\ \dfrac {999 \cdots 999}9 &= q \cdot n\\ \Downarrow\\ n &\mid 111 \cdots 111 ~~ \square \end{aligned} $$