오일러 정리Permalink

LemmaPermalink

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

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

$\phi(n)$의 원소들

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

증명

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

이 되기 때문에 모순이다.

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

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

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

그런데 $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 오일러 정리 ⭐️Permalink

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

증명 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)}$과 합동이다.

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

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

오일러 정리와 페르마 정리

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

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

증명 2

귀납법을 사용하자.

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

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

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

또한 다음을 보자.

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

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

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

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

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

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

결국,

오일러 정리의 활용Permalink

중국인의 나머지 정리Permalink

모두 서로소인 $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$인 어떤 정수를 나눈다.Permalink

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

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