페팽 소수판정법

개요

페핀의 판정법(Pépin's test)은 페르마 수 [math]\displaystyle{ F_n=2^{2^n}+1 }[/math]의 소수 여부를 판정할 수 있게 하는 정리이다.

진술

페르마 수 [math]\displaystyle{ F_n=2^{2^n}+1 }[/math]이 소수일 필요충분조건은

[math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1\pmod{F_n} }[/math]

이다.

증명

[math]\displaystyle{ F_n=2^{2^n}+1 }[/math]이 소수라고 가정하자. 그러면 이차상반성에 의해

[math]\displaystyle{ \left(\frac{3}{F_n}\right)=(-1)^{\frac{3-1}{2}\frac{F_n-1}{2}}\left(\frac{F_n}{3}\right) }[/math]

인데,

[math]\displaystyle{ F_n \equiv (-1)^{2^n} +1 \equiv 2 \pmod 3 }[/math]

이므로

[math]\displaystyle{ \left(\frac{3}{F_n}\right) =\left(\frac{2}{3}\right)=-1 }[/math]

이다. 한편 오일러의 규준에 의해

[math]\displaystyle{ \left(\frac{3}{F_n}\right) \equiv 3^{(F_n-1)/2}\pmod{F_n} }[/math]

이므로

[math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1\pmod{F_n} }[/math]

이다.

이제 [math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1\pmod{F_n} }[/math]이라고 가정하고 [math]\displaystyle{ p }[/math]를 [math]\displaystyle{ F_n }[/math]의 소인수라고 하자. 그러면 [math]\displaystyle{ p=F_n }[/math]임을 보이면 된다. [math]\displaystyle{ p \mid F_n }[/math]이므로

[math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1 \pmod p }[/math]

이고

[math]\displaystyle{ 3^{F_n-1}\equiv 1\pmod p }[/math]

이다. [math]\displaystyle{ \frac{F_n-1}{2}=2^{2^n-1} }[/math]이고 [math]\displaystyle{ F_n-1=2^{2^n} }[/math]이므로 [math]\displaystyle{ r=\operatorname{ord}_p 3 }[/math]이라 하면 위수의 성질에 의해 [math]\displaystyle{ r\mid 2^{2^n} }[/math]이고 [math]\displaystyle{ r\not\mid 2^{2^n-1} }[/math]이다. 따라서 [math]\displaystyle{ r=\operatorname{ord}_p 3 =F_n -1 }[/math]이다. 그러면

[math]\displaystyle{ F_n-1\le \operatorname{ord}_p 3 \le p-1 \le F_n-1 }[/math]

이므로 [math]\displaystyle{ p=F_n }[/math]을 얻는다. 따라서 [math]\displaystyle{ F_n }[/math]은 소수이다.