|
'''프로트의 정리'''는 [[수론]]에서 [[프로트 수]]에 대한 [[소수 판별법]]이다.
만일 ''<math>p''</math>가 ''<math>k'' < 2<sup>''^n''</supmath>이고, 홀수 ''<math>k''</math>를 갖는 ''k''2<supmath>''k \cdot 2^n''</sup> + 1 </math>형태의 [[프로트 수]]라면일 때, 어떤 [[정수]] ''<math>a''</math>에 대해서 다음과 같이 진술될 수 있다면,
:<math>a^{(\frac {p-1)/} 2} \equiv -1 \pmod{p}\,\!</math>
''<math>p''</math>는 [[소수 (수론)|소수]](이 소수는 '''[[프로트 소수''']]라고 불린다.)이다. 이 소수 판별법은 매우 단순하고 유용하다.
== 적용 예제 ==
프로트 정리를 적용하면 다음과 같다:
* <math>p = 3일때3</math>일때, <math>2^{(\frac {3-1)/} 2}</math> + 1 = 2<sup>^1</sup> + 1 = 3는3</math>는 3으로 나누어 떨어진다. 그러므로 3은 소수이다.
* <math>p = 5일때5</math>일때, <math>3^{(\frac {5-1)/} 2}</math> + 1 = 3<sup>^2</sup> + 1 = 10는10</math>는 5로 나누어 떨어진다. 그러므로 5는 소수이다.
* <math>p = 13일때13</math>일때, <math>5^{(\frac {13-1)/} 2}</math> + 1 = 5<sup>^6</sup> + 1 = 15626는15626</math>는 13으로 나누어 떨어진다. 그러므로 13은 소수이다.
* <math>p = 9일때9</math>일때, 소수가 아니므로 9로 나누어 떨어지는 수 ''a''<supmath>a^4 + 1</supmath>의 + 1의 ''<math>a''</math>는 존재하지 않는다.
프로트 소수는 다음과 같다. {{OEIS|id=A080076}}:
:[[3]], [[5]], [[13]], [[17]], [[41]], [[97]], [[113]], [[193]], [[241]], [[257]], [[353]], [[449]], [[577]], [[641]], [[673]], [[769]], [[929]], 1153
[[2007년 현재]], 알려진 것 중에서 가장 큰 프로트 소수는 19249 ·× 2<sup>13018586</sup> + 1이고 [[분산 컴퓨팅]] 프로젝트인 Seventeen or Bust에 의해 발견되었다. 이 소수의 자릿수는 3918990 이고, [[메르센 소수]]가 아닌 가장 큰 소수이다. <ref>[http://primes.utm.edu/top20/page.php?id=3 최대 소수 기록]</ref>
== 역사 ==
| 