프로트 수

1. 개요

프로트 수는 k * 2ⁿ + 1 (k는 홀수, n은 양의 정수) 형태로 표현되는 정수를 의미한다. 프로트 소수는 소수인 프로트 수를 지칭하며, 프로트의 정리를 통해 소수 여부를 판별할 수 있다. 2016년 기준으로, 10223×2^31172165 + 1이 발견된 가장 큰 프로트 소수이며, 9,383,761자리의 크기를 가진다.

2. 프로트 수

프로트 수는 프로트 수/Proth number^영어는 k * 2ⁿ + 1 ($k$는 홀수, $n$은 양의 정수) 형태로 표현되는 정수이다.

예를 들면, 프로트 수는 다음과 같다.
:P₀ = 1 × 2¹ + 1 = 3
:P₁ = 1 × 2² + 1 = 5
:P₂ = 1 × 2³ + 1 = 9
:P₃ = 3 × 2² + 1 = 13
:P₄ = 1 × 2⁴ + 1 = 17
:P₅ = 3 × 2³ + 1 = 25
:P₆ = 1 × 2⁵ + 1 = 33

이와 같은 방법으로 1000보다 작은 프로트 수를 정리하면 다음과 같다.
:3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993, …

프로트 소수(소수인 프로트수)는 다음과 같다.
:3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857, …

프로트 소수는 무수히 많을 것으로 예상되지만, 아직 증명되지 않았다.

프로트의 정리를 사용하여 프로트수가 소수인지 아닌지 판별할 수 있다。

p를 프로트수라고 하자. 다음의 합동식을 만족하는 정수 a가 있다면, p는 프로트 소수이다. 그렇지 않다면, 프로트 소수가 아니다.

:a^(p-1)/2 ≡ -1 (mod p)

즉, a^(p-1)/2에 1을 더한 수가 p로 나누어 떨어지도록 a를 찾으면 된다.

2016년 기준으로, 발견된 가장 큰 프로트 소수는 10223×2^31172165 + 1 이며, 9,383,761자리의 크기를 가진다。 이것이 소수라는 것은 PrimeGrid 프로젝트의 Péter Szabolcs에 의해 2016년 11월 6일에 발표되었다。 이 수는 메르센 소수가 아닌 알려진 가장 큰 소수이기도 하다。

2.1. 예시

프로트 수의 예시는 다음과 같다:

:3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993, …

*P*₀ = 1 × 2¹ + 1 = 3

*P*₁ = 1 × 2² + 1 = 5

*P*₂ = 1 × 2³ + 1 = 9

*P*₃ = 3 × 2² + 1 = 13

*P*₄ = 1 × 2⁴ + 1 = 17

*P*₅ = 3 × 2³ + 1 = 25

*P*₆ = 1 × 2⁵ + 1 = 33

3. 프로트 소수

프로트 소수(Proth prime)는 소수인 프로트 수를 말한다. 프로트의 정리는 주어진 프로트 수가 소수인지 판별하는 데 사용될 수 있다.

1만보다 작은 프로트 소수는 다음과 같다.
: 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857, …

프로트 소수는 무수히 많을 것으로 예상되지만, 아직 증명되지 않았다.

프로트의 정리를 사용하여 프로트수가 소수인지 아닌지 판별할 수 있다.
$p$를 프로트수라고 하자. 다음의 합동식을 만족하는 정수 $a$가 있다면, $p$는 프로트 소수이다. 그렇지 않다면, 프로트 소수가 아니다.

:$a^{(p-1)/2}\equiv -1\pmod{p}$

즉, $a^{(p-1)/2}$에 1을 더한 수가 $p$로 나누어 떨어지도록 $a$를 찾으면 된다.

2016년 기준으로, 발견된 가장 큰 프로트 소수는 10223×2^31172165 + 1 이며, 9,383,761자리의 크기를 가진다. 이것이 소수라는 것은 PrimeGrid 프로젝트의 페테르 서볼치/Péter Szabolcs^영어에 의해 2016년 11월 6일에 발표되었다. 이 수는 메르센 소수가 아닌 알려진 가장 큰 소수이기도 하다.

3.1. 프로트 소수 판별법

프로트의 정리를 사용하여 프로트 수가 소수인지 아닌지 판별할 수 있다. $p$를 프로트 수라고 할 때, 다음 합동식을 만족하는 정수 $a$가 있다면 $p$는 프로트 소수이다. 그렇지 않다면, 프로트 소수가 아니다.

:$a^{(p-1)/2}\equiv -1\pmod{p}$

즉, $a^{(p-1)/2}$에 1을 더한 수가 $p$로 나누어 떨어지도록 $a$를 찾으면 된다.

2016년 기준으로, 발견된 가장 큰 프로트 소수는 10223×2^31172165 + 1 이며, 9,383,761자리의 크기를 가진다. 이것이 소수라는 것은 PrimeGrid 프로젝트의 페테르 서볼치/Péter Szabolcs^영어에 의해 2016년 11월 6일에 발표되었다. 이 수는 메르센 소수가 아닌 알려진 가장 큰 소수이기도 하다.

3.2. 프로트 소수 목록

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 …

3.3. 최대 프로트 소수

2016년 11월, PrimeGrid 프로젝트의 서볼치 페테르/Szabolcs Péter^헝가리어는 당시 기준으로 가장 큰 프로트 소수인 10223 × 2^31172165 + 1을 발견했다. 이 수는 9,383,761자리이며, 메르센 소수가 아닌 알려진 가장 큰 소수이다.

4. 관련 정리 및 프로젝트

프로트의 정리는 주어진 프로트 수가 소수인지를 판정하는 테스트로 사용될 수 있다. 만약 2의 거듭제곱($2^n$)에 그보다 작은 홀수를 곱하고 1을 더한 수($k\; \backslash cdot\; 2^n\; +\; 1$)가 소수인 경우, 즉 프로트 수가 소수이면 이를 프로트 소수(Proth prime)라고 한다.

1만보다 작은 프로트 소수는 다음과 같다.
: 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857, …