📂정수론

페르마의 소정리 증명

정리 ¹

소수 $p$ 와 서로소인 정수 $a$ 에 대해, $a^{p-1} \equiv 1 \pmod{p}$

설명

페르마의 소정리는 단순하지만 아주 많은 곳에 쓰이는 정리 중 하나다. 오일러에 의해 일반화된 정리도 있지만 페르마의 소정리로도 충분한 경우가 많기 때문이다. 특히 유한체에서의 거듭제곱을 많이 다루는 암호론 등에서는 필수적인 정리다.

증명

전략: 증명은 단순무식하지만 그만큼 간단하지는 않다. 만약 $$ a \cdot 2a \cdot \cdots \cdot (p-1)a \equiv (p-1)! \pmod{p} $$ 가 성립한다면 양변의 $(p-1)!$를 소거시켜 페르마의 소정리를 증명할 수 있을 것이다. 즉 두 집합 $\left\{ a,2a,\cdots , (p-1)a \right\}$ 와 $\left\{1,2,\cdots ,(p-1) \right\}$ 가 $\pmod{p}$ 에서 같음을 보이면 된다.

---

집합 $\left\{ a,2a,\cdots , (p-1)a \right\}$ 은 정확하게 $(p-1)$ 개의 원소를 가진 유한 집합이다. $a$ 가 $p$ 와 서로소이므로, 이 원소들을 $p$ 로 나눈 나머지는 $1$ 부터 $(p-1)$ 까지의 정수 중 하나일 것이다. 그리고 그 나머지에 중복이 없다면 $$ \left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots ,(p-1) \right\} $$ 이 성립할 것이다. $\left\{ a,2a,\cdots , (p-1)a \right\}$ 에서 서로 다른 임의의 두 원소 $ia$와 $ja$ 를 가져와 생각해보자. 이 둘을 $p$로 나눈 나머지가 같다고 가정하면, $ia \equiv ja \pmod{p}$가 성립한다. $a$가 $p$와 서로소이므로 양변에서 $a$를 소거하면 $i \equiv j \pmod{p}$ 역시 성립한다. 그런데 위 집합에서 $i$와 $j$ 는 $0$보다 크고 $p$보다 작은 정수였으므로 $ia$와 $ja$도 같다. 이는 가정에 모순이므로, 서로 다른 임의의 두 원소를 $p$로 나눈 나머지는 항상 다르다는 걸 알 수 있다. 나머지에 중복이 없으므로, $\pmod{p}$에서 $$ \left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots ,(p-1) \right\} $$ 이 성립한다. 한편 $p$ 는 소수이므로 $(p-1)!$ 과 서로소다. $$ (p-1)! a^{p-1} \equiv (p-1)! \pmod{p} $$ 에서 양변의 $(p-1)!$ 를 소거시키면 합동식 $a^{p-1} \equiv 1 \pmod{p}$ 를 얻는다.

■

아래의 따름정리도 알아두도록하자.

따름정리

• [1] 역원: $\pmod{p}$ 에서 곱셈에 대한 $a$ 의 역원은 반드시 이렇게 주어진다. $$ a^{-1} \equiv a^{p-2} \pmod{p} $$
• [2] 페르마 판정법: $a^n \equiv a \pmod{n}$ 이 성립하지 않는다면 $n$ 은 합성수다.

어떤 수가 소수인지 판별하는 것은 쉽지 않지만 합성수라는 것은 비교적 판별하기가 쉽다. 주의해야할 것은 페르마 판별법의 역은 성립하지 않는다는 것이다. 특히 역이 성립하지 않는다는 걸 보여주는 반례로는 카마이클 수가 있다. 카마이클 수의 예로써 $561=3 \cdot 11 \cdot 17$ 은 합성수지만 $a^{561} \equiv a \pmod{561}$ 이 항상 성립한다.

코드

다음은 페르마 판정법을 R 로 구현한 것으로, 계산을 위해 연속제곱법이 쓰였다.

FPM<-function(base,power,mod) #It is equal to (base^power)%%mod
{
  i<-0
  if (power<0) {
    while((base*i)%%mod != 1) {i=i+1}
    base<-i
    power<-(-power)}
  
  if (power==0) {return(1)}
  if (power==1) {return(base%%mod)}
  
  n<-0
  while(power>=2^n) {n=n+1}
  
  A<-rep(1,n)
  A[1]=base
  
  for(i in 1:(n-1)) {A[i+1]=(A[i]^2)%%mod}
  
  for(i in n:1) {
    if(power>=2^(i-1)) {power=power-2^(i-1)}
    else {A[i]=1} }
  
  for(i in 2:n) {A[1]=(A[1]*A[i])%%mod}
  
  return(A[1])
}
 
fermat.test<-function(n)
{
  for(i in 2:(n-1))  {if( i!=FPM(i,n,n) ) {return(paste(i,"is a Fermat witness!"))}}
  paste(n,"passes the Fermat test!")
}
 
fermat.test(121)
fermat.test(341)    #Almost composite yields fermat witness 2, but 341=11*31 doesn't.
fermat.test(561)    #Carmicheal number 561 = 3*11*17
fermat.test(1031)    #1031 is a prime
fermat.test(1105)    #Carmicheal number 1105 = 5*13*17
fermat.test(1729)    #Carmicheal number 1729 = 7*13*19
fermat.test(41041)    #Carmicheal number 41041 = 7*11*13*41

다음은 코드를 실행시킨 결과다.

페르마 판정법은 $121$ 이나 $341$ 과 같은 합성수는 확실히 잡아낼 수 있었고, $1031$ 같은 소수는 제대로 통과시켰다. 그러나 $561$, $1105$, $1729$, $41041$ 과 같은 카마이클 수는 잡아낼 수 없었다. 카마이클 수를 잡아내려면 밀러-라빈 판정법과 같은 방법을 동원해야한다.