프로트의 정리

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

a^{\frac{p - 1}{2}} \equiv - 1 (\mod 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$ 는 존재하지 않는다.

가장 작은 프로트 소수부터 차례대로 나열하면 다음과 같다. 틀:OEIS:

2020년을 기준으로 지금까지 알려진 프로트 소수 중에서 가장 큰 수는 2016년에 발견된 10223 × 2^31172165 + 1이다. 이 소수는 9,383,761자리이고, 현재까지 발견된 소수들 중 메르센 소수가 아닌 소수 중에서는 가장 큰 소수이다.^[1]

농부였던 아마추어 수학자, 프랑수아 프로트 (1852년 - 1879년)는 1878년경에 이 정리를 발견했다.