프로트의 정리 문서 원본 보기

{{위키데이터 속성 추적}}
'''프로트의 정리'''는 [[수론]]에서 [[프로트 수]]에 대한 [[소수 판별법]]이다.

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

:<math>a^{\frac {p-1} 2} \equiv -1 \pmod{p}</math>

<math>p</math>는 [[소수 (수론)|소수]] (이때 이 소수는 [[프로트 소수]]라고 한다)이다. 이 소수 판별법은 프로트 수에 대해서는 매우 단순하고 유용하다.

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

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

가장 작은 프로트 소수부터 차례대로 나열하면 다음과 같다. {{OEIS|A080076}}:
:[[3]], [[5]], [[13]], [[17]], [[41]], [[97]], [[113]], [[193]], [[241]], [[257]], [[353]], [[449]], [[577]], [[641]], [[673]], [[769]], [[929]], 1153

2020년을 기준으로 지금까지 알려진 프로트 소수 중에서 가장 큰 수는 2016년에 발견된 10223 × 2<sup>31172165</sup> + 1이다. 이 소수는 9,383,761자리이고, 현재까지 발견된 소수들 중 [[메르센 소수]]가 아닌 소수 중에서는 가장 큰 소수이다.<ref>[http://primes.utm.edu/top20/page.php?id=3 최대 소수 기록]</ref>

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

== 같이 보기 ==
* [[시에르핀스키 수]]

== 각주 ==
<references />

== 외부 링크 ==
* {{매스월드|id=ProthsTheorem|title=Proth's Theorem}}

{{수론 알고리즘}}

[[분류:소수 판별법]]
[[분류:소수에 관한 정리]]