프로트 수

수론에서 프로트 수(Proth number)는 2의 거듭제곱( $2^{n}$ )에 그보다 작은 홀수를 곱하고 1을 더한 수로, 식으로 나타내면 다음과 같다.

P=k\cdot 2^{n}+1

여기서 $k$ 는 홀수이고, $n$ 은 양의 정수이며 $2^{n}>k$ 이다. 프로트 수는 프랑스의 수학자 프랑수아 프로트(François Proth)의 이름을 따서 명명되었다.^[1]

예시

예를 들면, 프로트 수는 다음과 같다. (OEIS의 수열 A080075)

{\begin{aligned}P_{0}&=1\times 2^{1}+1&=3\\P_{1}&=1\times 2^{2}+1&=5\\P_{2}&=1\times 2^{3}+1&=9\\P_{3}&=3\times 2^{2}+1&=13\\P_{4}&=1\times 2^{4}+1&=17\\P_{5}&=3\times 2^{3}+1&=25\\P_{6}&=1\times 2^{5}+1&=33\\\end{aligned}}

이와 같은 방법으로 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의 거듭제곱( $2^{n}$ )에 그보다 작은 홀수를 곱하고 1을 더한 수( $k\cdot 2^{n}+1$ )가 소수(素數)인 경우, 즉 프로트 수가 소수이면 이를 ‘프로트 소수(Proth prime)’라고 한다. 프로트의 정리는 주어진 프로트 수가 소수인지를 판정하는 테스트로 사용될 수 있다.