Number Theory - 5.2 페르마의 소정리와 유사소수
5장 페르마 정리 단원에 대해서 알아보자.
PS에 쓰자면 페르마 정리만 중요하게 생각하면 되긴 할텐데, 뒤에 유사소수까지 증명내용이 긴 단원이다.
페르마 정리
페르마의 소정리라고도 불린다.
Theorem 5.1 페르마 정리
$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$
$p$가 $a$를 나누지 않는다는 조건이 없어진 일반적인 따름정리가 있다.
Corollary 1
$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 Lemma
$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$ 이여도 성립한다.
페르마 정리와 소수 검사
어떤 $a$에 대해 $a^p \equiv a \pmod p$ 가 성립하지 않으면 $a$는 합성수이다.
그러나 이것이 만족한다고 $p$가 소수인것은 아니다.
위 식을 만족하는 $p$중, 소수가 아닌 수를 절대 유사 소수나 카마이클 수라고 한다.
왜 역이 성립하지 않는지 보자.
Lemma
$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$
유사 소수
합성수 $n$에 대해,
$2^n \equiv 2 \pmod n$ 이면, $n$을 유사 소수라고 한다.
위를 만족하는 $n$이 소수라는 주장은 $n=341$에 의해 반례가 있다.
$n$이 소수이면 당연히 성립하므로, $n$이 합성수일 때로 조건이 제한된다.
무수히 많은 유사소수가 존재하며, 이러한 유사소수들의 증가수열을 만들 수 있는 정리가 있다.
Theorem 5.2
$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$
절대 유사소수, 카마이클 수
앞서 다룬 유사소수는 기저 $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.3
$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$
Comments