프로트 소수

프로트 수(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)

1 특징[편집]

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

  • 어떤 프로트 수 [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이 아닐 때까지 시도한다.

2 알려진 가장 큰 소수[편집]

아래는 2022년 8월 23일까지 발견된 가장 큰 프로트 소수들이다.[1] 표에서 가장 큰 값인 [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][2] 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월

3 같이 보기[편집]

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

4 각주

  1. Prime Pages, Top twenty: Proth primes
  2. [math]\displaystyle{ k=2^{7658613}+1, n=7658614 }[/math]