개요
페핀의 판정법(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]이라고 가정하고 \(p\)를 \(F_n\)의 소인수라고 하자. 그러면 \(p=F_n\)임을 보이면 된다. \(p \mid F_n\)이므로
- [math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1 \pmod p }[/math]
이고
- [math]\displaystyle{ 3^{F_n-1}\equiv 1\pmod p }[/math]
이다. \(\frac{F_n-1}{2}=2^{2^n-1}\)이고 \(F_n-1=2^{2^n}\)이므로 \(r=\operatorname{ord}_p 3\)이라 하면 위수의 성질에 의해 \(r\mid 2^{2^n}\)이고 \(r\nmid 2^{2^n-1}\)이다. 따라서 \(r=\operatorname{ord}_p 3 =F_n -1\)이다. 그러면
- [math]\displaystyle{ F_n-1\le \operatorname{ord}_p 3 \le p-1 \le F_n-1 }[/math]
이므로 \(p=F_n\)을 얻는다. 따라서 \(F_n\)은 소수이다.