프로트 수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 프로트 수
- 2.1. 예시
3. 프로트 소수
4. 관련 정리 및 프로젝트
참조

1. 개요

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

더 읽어볼만한 페이지

수론 - 타원곡선
타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
수론 - 최소공배수
최소공배수는 둘 이상의 정수들의 공배수 중 가장 작은 양의 정수로서, 소인수분해나 최대공약수와의 관계를 이용하여 구할 수 있으며, 분수 통분이나 기어 회전 수 계산 등 여러 분야에 응용된다.

프로트 수
일반 정보
종류	자연수
속성	홀수 정수 자연수
정의	k × 2ⁿ + 1 (단, k는 홀수, 2ⁿ > k) 형태의 수
관련 정보
관련 항목	페르마 수 소수 프로스 소수
추가 정보
미해결 문제	프로스 소수가 무수히 많은가?

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, …

'''프로트 소수'''(소수인 프로트수)는 다음과 같다.^[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]。

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자리의 크기를 가진다^[4]。 이것이 소수라는 것은 PrimeGrid 프로젝트의 Péter Szabolcs에 의해 2016년 11월 6일에 발표되었다^[5]。 이 수는 메르센 소수가 아닌 알려진 가장 큰 소수이기도 하다^[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)는 소수인 프로트 수를 말한다.^[2] 프로트의 정리는 주어진 프로트 수가 소수인지 판별하는 데 사용될 수 있다.

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, …

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

프로트의 정리를 사용하여 프로트수가 소수인지 아닌지 판별할 수 있다.^[3]

$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자리의 크기를 가진다.^[4] 이것이 소수라는 것은 PrimeGrid 프로젝트의 페테르 서볼치/Péter Szabolcs^영어에 의해 2016년 11월 6일에 발표되었다.^[5] 이 수는 메르센 소수가 아닌 알려진 가장 큰 소수이기도 하다.^[6]

3. 1. 프로트 소수 판별법

프로트의 정리를 사용하여 프로트 수가 소수인지 아닌지 판별할 수 있다.^[3] $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자리의 크기를 가진다.^[4] 이것이 소수라는 것은 PrimeGrid 프로젝트의 페테르 서볼치/Péter Szabolcs^영어에 의해 2016년 11월 6일에 발표되었다.^[5] 이 수는 메르센 소수가 아닌 알려진 가장 큰 소수이기도 하다.^[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^hu는 당시 기준으로 가장 큰 프로트 소수인 10223 × 2^31172165 + 1을 발견했다. 이 수는 9,383,761자리이며, 메르센 소수가 아닌 알려진 가장 큰 소수이다.

4. 관련 정리 및 프로젝트

프로트의 정리는 주어진 프로트 수가 소수인지를 판정하는 테스트로 사용될 수 있다. 만약 2의 거듭제곱( $2^n$ )에 그보다 작은 홀수를 곱하고 1을 더한 수( $k \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, …

참조

_[1] MathWorld Proth Number
_[2] MathWorld Proth Prime
_[3] MathWorld Proth's Theorem
_[4] 웹사이트 The Top Twenty: Proth http://primes.utm.ed[...]
_[5] 웹사이트 World Record Colbert Number discovered! http://www.primegrid[...] 2016-12-07
_[6] 웹사이트 The Top Twenty: Largest Known Primes http://primes.utm.ed[...]
_[7] arXiv 인용 Deterministic Primality Proving on Proth Numbers

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com