프로트의 정리

만일 $p$ 가 $k<2^{n}$ 이고, 홀수 $k$ 를 갖는 $k\cdot 2^{n}+1$ 형태의 프로트 수일 때, 어떤 정수 $a$ 에 대해서 다음과 같이 표현될 수 있다면,

a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

$p$ 는 소수 (이때 이 소수는 프로트 소수라고 한다)이다. 이 소수 판별법은 프로트 수에 대해서는 매우 단순하고 유용하다.

적용 예제 편집

프로트 정리를 적용하면 다음과 같다:

$p=3$ 일 때, $2^{\frac {3-1}{2}}+1=2^{1}+1=3$ 는 3으로 나누어떨어진다. 그러므로 3은 소수이다.
$p=5$ 일 때, $3^{\frac {5-1}{2}}+1=3^{2}+1=10$ 는 5로 나누어떨어진다. 그러므로 5는 소수이다.
$p=13$ 일 때, $5^{\frac {13-1}{2}}+1=5^{6}+1=15626$ 는 13으로 나누어떨어진다. 그러므로 13은 소수이다.
$p=9$ 일 때, 소수가 아니므로 9로 나누어떨어지는 수 $a^{4}+1$ 의 $a$ 는 존재하지 않는다.