프로트의 정리

프로트의 정리는 수론에서 프로트 수에 대한 소수 판별법이다.

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

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

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

적용 예제

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

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

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

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153

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

역사

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

같이 보기

• 시에르핀스키 수