프로트의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

프로트의 정리수론에서 프로트 수에 대한 소수 판별법이다.

만일 pk < 2^n이고, 홀수 k를 갖는 k \cdot 2^n + 1형태의 프로트 수일 때, 어떤 정수 a에 대해서 다음과 같이 진술될 수 있다면,

a^{\frac {p-1} 2} \equiv -1 \pmod{p}

p소수(이 소수는 프로트 소수라고 불린다.)이다. 이 소수 판별법은 매우 단순하고 유용하다.

적용 예제[편집]

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

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

프로트 소수는 다음과 같다. (OEIS의 수열 A080076):

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153

2013년 기준으로, 알려진 것 중에서 가장 큰 프로트 소수는 2007년에 분산 컴퓨팅 프로젝트인 Seventeen or Bust에 의해 발견되된 19249 × 213018586 + 1이다. 이 소수의 자릿수는 3918990 이고, 메르센 소수가 아닌 가장 큰 소수이다. [1]

역사[편집]

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

같이 보기[편집]

주석[편집]

  1. 최대 소수 기록

바깥 고리[편집]