5장 페르마 정리 단원에 대해서 알아보자.

PS에 쓰자면 페르마 정리만 중요하게 생각하면 되긴 할텐데, 뒤에 유사소수까지 증명내용이 긴 단원이다.

페르마 정리Permalink

페르마의 소정리라고도 불린다.

Theorem 5.1 페르마 정리Permalink

$p$가 소수이고 $p \nmid a$이면, $a^{p-1} \equiv 1 \pmod p$

증명

$a$의 $p-1$개의 배수를 본다.

이는 법 $p$에 대해 완전잉여계를 이룬다.

그렇지 않다면 $ia \equiv ja \pmod p ~~(i \ne j, ~0 \le i,j <p)$ 인 $i,j$ 가 존재하여 $gcd(a,p)=1$ 이라서 양변에서 $a$를 소거하면

$i - j \equiv 0 \pmod p$라서 $1 \le \lvert i-j \rvert \le p-1$ 인데 이걸 $p$가 나눈다는건 모순이다.

따라서 위의 정수들은 어떤 순서로 $0,1,\dots,p-1$에 법 $p$에 대해 합동이다.

모든 합동식을 곱해주면

이다. $gcd((p-1)!, p)=1$ 이므로, 양변에서 $(p-1)!$을 소거하여

$a^{p-1} \equiv 1 \pmod p ~~ \square$Permalink

$p$가 $a$를 나누지 않는다는 조건이 없어진 일반적인 따름정리가 있다.

Corollary 1Permalink

$p$를 소수라 하면, 모든 정수 $a$에 대해 $a^p \equiv a \pmod p$

증명

$p \mid a$ 이면 $a=kp$이고 $a^p=(kp)^p \equiv kp \equiv 0 \pmod p$

이므로 성립한다.

$p \nmid a$ 이면 페르마 정리에 의해

증명에서 쓰이진 않았지만, 이항정리에서 소수에 대해 유용히 쓰이는 보조정리가 하나 있다.

이는 뤼카정리에서의 증명에서도 쓰이는 보조정리이다.

Bonus LemmaPermalink

$p$가 소수라면 모든 정수 $a$에 대해

증명

좌변을 전개하면(이항정리),

$1 \le i \le p-1$ 인 $i$에 대해 $\dbinom{p}{i}=\dfrac {p!}{(p-i)!i!} \nmid p$ 이기 때문에, $p \mid \dbinom{p}{i}$이다.

따라서 법 $p$에 대한 합동식에서는 중간에 항들이 모두 소거되어

이제 이 보조정리를 이용해서 다시 $a^p \equiv a \pmod p$ 를 증명할 수 있다.

증명

$a=1$ 일 때, $1^p \equiv 1 \pmod p$ 이므로 성립

$a^p \equiv a \pmod p$라 하고, $a+1$ 에대해 식을 써보면,

$(a+1)^p \equiv a+1 \pmod p$

그런데 위의 보조정리에 의해 $(a+1)^p \equiv a^p+1 \pmod p$ 이므로,

귀납가정에 의해 $a^p \equiv a \pmod p$ 이기 때문에

이는 $a < 0$ 이여도 성립한다.

페르마 정리와 소수 검사Permalink

어떤 $a$에 대해 $a^p \equiv a \pmod p$ 가 성립하지 않으면 $a$는 합성수이다.

그러나 이것이 만족한다고 $p$가 소수인것은 아니다.

위 식을 만족하는 $p$중, 소수가 아닌 수를 절대 유사 소수나 카마이클 수라고 한다.

왜 역이 성립하지 않는지 보자.

LemmaPermalink

$p$와 $q$가 서로 다른 소수이고,

$a^p \equiv a \pmod q$이고 $a^q \equiv a \pmod p$이면, $a^{pq} \equiv a \pmod {pq}$

증명

$(a^q)^p \equiv a^q \pmod p$ 이고, 가정에 의해 $a^q \equiv a \pmod p$ 이므로,

$a^{pq} \equiv a \pmod p$ 를 유도하고, 동일하게 $a^{pq} \equiv \pmod q$

$gcd(p,q)=1$ 이므로, $pq \mid a^{pq}-a \Longrightarrow a^{pq} \equiv \pmod {pq} \square$

유사 소수Permalink

합성수 $n$에 대해,

$2^n \equiv 2 \pmod n$ 이면, $n$을 유사 소수라고 한다.

위를 만족하는 $n$이 소수라는 주장은 $n=341$에 의해 반례가 있다.

$n$이 소수이면 당연히 성립하므로, $n$이 합성수일 때로 조건이 제한된다.

무수히 많은 유사소수가 존재하며, 이러한 유사소수들의 증가수열을 만들 수 있는 정리가 있다.

Theorem 5.2Permalink

$n$이 홀수인 유사소수이면, $M_n=2^n-1$ 은 더 큰 유사소수이다.

증명

$n$이 합성수이므로, $n=rs, 1 < r \le s < n$ 라고 하자.

$k_1 \mid k_2$ 일 때, $a^{k_1}-1 \mid a^{k_2}-1$ 이므로, $2^r-1 \mid 2^n-1$ 이다.

즉, $2^n-1$은 합성수이다.

$n$이 유사소수여서 $2^n \equiv 2 \pmod n$이므로, 어떤 $k$에 대해

이므로, $2^{M_n-1} \equiv 1 \pmod {M_n}$의 양변에 $2$를 곱하면,

$2^{M_n}\equiv 2 \pmod {M_n}$

따라서 $M_n$은 유사소수이다. $\square$

절대 유사소수, 카마이클 수Permalink

앞서 다룬 유사소수는 기저 $2$에 대해 나온 개념이다.

모든 기저 $a$에 대해 유사 소수인 $n$은 절대 유사소수라고 한다.

즉, 모든 $a$에 대해 $a^n \equiv a \pmod n$

절대 유사소수 = 카마이클 수이고, $561, 1105, 2821, 15841$ 같은 것이 있다.

이는 $1,000,000$이하의 수중에 단지 $43$개밖에 없을 정도로 희소하다.

$561$이 절대 유사소수임을 보이자.

$561=3 \cdot 11 \cdot 17$이고

$gcd(a,561)=1$ 이라면,

$gcd(a, 561) \ne 1$ 이라면 항상 $a^{561} \equiv a \pmod {561}$이 성립한다.

이므로, 페르마 정리를 이용해

이 되고,

$gcd(a,b)$ 일 때, $a \mid c,~b \mid c$이면, $ab \mid c$ 이므로

$a^{560} \equiv 1 \pmod {561} \Longrightarrow a^{561} \equiv a \pmod {561} ~~ \square$

절대 유사소수는 제곱 인수가 없는 수이다.

증명

모든 정수 $a$에 대해 $a^n \equiv a \pmod n$일 때,

어떤 $k>1$ 에 대해 $k^2 \mid n$이라고 가정하자.

$a=k$ 라 두면,

$k^n \equiv k \pmod n$ 이고, $k^2$는 $n$의 약수이므로 법 $k^2$에 대해서도 합동식이 성립해야 하므로

$0 \equiv k^2 \equiv k \pmod {k^2}$ 인데 그럼 $k^2 \mid k$가 되어서 모순이다. $\square$

Theorem 5.3Permalink

$n$을 제곱인수가 없는 합성수라 하자.

$i=1,2,\dots,r$ 에 대해 $p_i-1 \mid n-1$ 이면 $n$은 절대유사소수이다.

증명

$a$를 $gcd(a,n)=1$ 을 만족하는 정수라 가정하여 모든 $i$에 대해 $gcd(a, p_i)=1$ 이다.

페르마 정리에 의해

$a^{p_i-1} \equiv 1 \pmod {p_i}$ 이므로 $p_i \mid a^{p_i-1}-1$

따라서 모든 정수 $a$ 그리고 $i=1,2,\dots,r$ 에 대해 $p_i \mid a^n-a$ 이다.

따라서 $n \mid a^n-a$ 이고 $a^n \equiv a \pmod n$ 이다. $\square$