프로트 소수

프로트 수(Proth number)는 [math]\displaystyle{ N=k\cdot 2^n+1 (k\lt 2^n) }[/math]의 형태로 표현되는 자연수이다. 프로트 소수(Proth prime)는 프로트 수 중 소수인 수를 가리킨다. 프랑스의 수학자 프랑수아 프로트(François Proth)에서 유래하였다.

처음 프로트 소수의 목록은 아래와 같다.

• 3, 5, 13, 17, 41, 97, 193, 241, 257, 353, … (OEIS의 수열 A080076)

특징

이와 관련한 내용은 프로트의 정리에서 볼 수 있습니다.

메르센 소수의 뤼카-레머 소수판정법처럼 특수한 큰 수를 빠르게 소수 판정하는 정리가 존재한다. 프로트의 정리는 프로트 수가 소수이기 위한 필요충분조건을 제시한다.

• 어떤 프로트 수 [math]\displaystyle{ N }[/math]이 소수이면 합동식 [math]\displaystyle{ a^{\frac{N-1}{2}} \equiv -1 \pmod N }[/math]인 정수 [math]\displaystyle{ a }[/math]가 존재하고, 그 역도 성립한다.

그렇다면 임의로 고른 [math]\displaystyle{ a }[/math]에 대해 위 합동식의 우변이 -1이 아닌 다른 값이 나온다면? [math]\displaystyle{ a^{\frac{N-1}{2}} \not\equiv \pm 1 \pmod N }[/math]이라면, 솔로베이-슈트라센 소수판정법에 의해 합성수임이 드러난다. [math]\displaystyle{ a^{\frac{N-1}{2}} \equiv 1 \pmod N }[/math]인 경우, 소수 여부를 알 수 없으며 [math]\displaystyle{ a }[/math]의 값을 바꿔서 합동식의 우변이 1이 아닐 때까지 시도한다.

알려진 가장 큰 소수

아래는 2022년 8월 23일까지 발견된 가장 큰 프로트 소수들이다. 표에서 가장 큰 값인 [math]\displaystyle{ 10223 \cdot 2^{31172165}+1 }[/math]는 현재까지 알려진 소수 중 메르센 소수를 제외하고 가장 큰 소수이다.

#	소수	자릿수	발견 일시
1	[math]\displaystyle{ 10223 \cdot 2^{31172165}+1 }[/math]	9383761	2016년 11월
2	[math]\displaystyle{ 202705 \cdot 2^{21320516}+1 }[/math]	6418121	2021년 12월
3	[math]\displaystyle{ 7 \cdot 2^{20267500}+1 }[/math]	6101127	2022년 7월
4	[math]\displaystyle{ 168451 \cdot 2^{19375200}+1 }[/math]	5832522	2017년 9월
5	[math]\displaystyle{ 7 \cdot 2^{18233956}+1 }[/math]	5488969	2020년 10월
6	[math]\displaystyle{ 3 \cdot 2^{16408818}+1 }[/math]	4939547	2020년 10월
7	[math]\displaystyle{ 2^{15317227}+2^{7658614}+1 }[/math]	4610945	2020년 7월
8	[math]\displaystyle{ 37 \cdot 2^{14166940}+1 }[/math]	4264676	2022년 6월
9	[math]\displaystyle{ 99739 \cdot 2^{14019102}+1 }[/math]	4220176	2019년 12월
10	[math]\displaystyle{ 404849 \cdot 2^{13764867}+1 }[/math]	4143644	2021년 3월
11	[math]\displaystyle{ 9 \cdot 2^{13334487}+1 }[/math]	4014082	2020년 3월
12	[math]\displaystyle{ 19249 \cdot 2^{13018586}+1 }[/math]	3918990	2007년 3월
13	[math]\displaystyle{ 9 \cdot 2^{12406887}+1 }[/math]	3734847	2020년 3월
14	[math]\displaystyle{ 27 \cdot 2^{12184319}+1 }[/math]	3667847	2021년 2월
15	[math]\displaystyle{ 37 \cdot 2^{11855148}+1 }[/math]	3568757	2022년 5월
16	[math]\displaystyle{ 41 \cdot 2^{11676439}+1 }[/math]	3514960	2022년 6월
17	[math]\displaystyle{ 9 \cdot 2^{11500843}+1 }[/math]	3462100	2020년 3월
18	[math]\displaystyle{ 193997 \cdot 2^{11452891}+1 }[/math]	3447670	2018년 4월
19	[math]\displaystyle{ 9 \cdot 2^{11366286}+1 }[/math]	3421594	2020년 3월
20	[math]\displaystyle{ 9 \cdot 2^{11158963}+1 }[/math]	3359184	2020년 3월

같이 보기

• 페르마 수: 프로트 수 중 [math]\displaystyle{ k=1, n=2^m }[/math]인 경우이다.
• 쿨렌 수: 프로트 수 중 [math]\displaystyle{ k=n }[/math]인 경우이다.