프로트의 정리

수 이론에서 프로스의 정리는 프로스 숫자에 대한 원시성 시험이다.

p가 Proth 번호인 경우 k2ⁿ + 1 형식(k 홀수 및 k < 2ⁿ), 그리고 a의 정수(instant a)가 있는 경우 다음과 같이 명시되어^[1][2] 있다.

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

p는 prime이다.이 경우 p를 프로스 프라임이라고 한다.p가 프라임이라면, 선택된 a는 일할 확률이 약 50%이기 때문에 이것은 실제 시험이다.

만약 a가 2차적 비residue modulo p인 경우, 그 반대도 또한 참이며, 테스트는 확정적이다.그러한 a는 다음과 같은 때까지 작은 프리타임을 반복하고 Jacobi 기호를 계산하면 찾을 수 있다.

${\displaystyle \왼쪽 \frac {a}{p}\오른쪽)=-1.}$

따라서, 많은 몬테카를로 원시성 시험(허위 양성을 반환할 수 있는 무작위 알고리즘)과는 대조적으로, 프로스의 정리에 기초한 원시성 시험 알고리즘은 라스베이거스 알고리즘으로, 항상 정답을 반환하지만 무작위로 변화하는 런닝 시간을 가지고 있다.

숫자 예제

정리의 예는 다음과 같다.

• p = 3 = 1(2¹) + 1의 경우, 2^(3-1)/2 + 1 = 3은 3으로 분할되므로 3은 prime이다.
• p = 5 = 1(2²) + 1의 경우, 3^(5-1)/2 + 1 = 10은 5로 분할되므로 5는 prime이다.
• p = 13 = 3(2²) + 1의 경우, 5^(13-1)/2 + 1 = 15626은 13으로 분할되므로 13은 프라임이다.
• p = 9에 대해, 프라임이 아닌 경우, + 1은^(9-1)/2 9로 나누어진다.

첫 번째 프로스 프리타임은 (OEIS에서 순서 A080076):

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

2016년^[update] 현재 가장 큰 것으로 알려진 프로스 프라임은 ${\displaystyle 10223}$ ${\displaystyle \cdot }$ 2 ${\displaystyle {31172165}^{}}$+ ${\displaystyle 1}$ $(\displaystyle 10223\cdot$ 2$^{3172165}+1}$이며$,$ 길이는 9383,761자리 입니다.^[3]그것은 2016년 11월 6일에 발표된 PrimeGrid 분산 컴퓨팅 프로젝트에서 Peter Szabolcs에 의해 발견되었다.^[4]이것은 또한 알려진 가장 큰 비 메르센 프라임과 가장 큰 콜버트 수이다.^[5]두 번째로 큰 것으로 알려진 프로스 프라임은 세븐틴 또는 버스트에 의해 ${\displaystyle \mathrm{발견}}$된 19249$130$ ${\displaystyle 2^{}}$ 13018586${\displaystyle {}^{}}$+ ${\displaystyle 1}$ ${\displaystyle 19249\cdot$ 2$^{13018586}+1$}이다$.$^[6]

증명

이 정리에 대한 증거는 포클링턴-레머의 원시성 테스트를 사용하며, 페핀의 시험과 매우 흡사하다.그 증거는 참고 문헌에서 리벤보임이 쓴 책의 52페이지에서 찾을 수 있다.

역사

프랑수아 프로트(1852–1879)는 1878년에 정리를 발표했다.^[7][8]

참고 항목

• Pépin의 검정(특수 케이스 k = 1, 여기서 a = 3)
• 시에르핀스키 수

참조

외부 링크

• Weisstein, Eric W. "Proth's Theorem". MathWorld.