페르마 수

1. 개요

페르마 수는 1637년 피에르 드 페르마가 2ⁿ+1 형태로 표현되는 정수가 소수일 것이라고 추측하면서 연구가 시작되었다. F0부터 F4까지는 소수였으나, 레온하르트 오일러가 F5를 소인수분해하여 페르마의 추측이 틀렸음을 증명했다. 페르마 수는 F_n = (F_n-1-1)²+1, F_n = F₀ … F_n-1 + 2 등의 성질을 가지며, 서로 다른 페르마 수는 서로소이다. 2ⁿ + 1 꼴의 소수인 페르마 소수는 F0=3, F1=5, F2=17, F3=257, F4=65537 뿐이며, 현재까지 n>4인 페르마 소수는 발견되지 않았다. 페르마 수는 정다각형 작도 가능성과 관련이 있으며, 일반화된 페르마 수는 $a^{2^n} + b^{2^n}$ 형태로 표현된다. 페르마 소수는 의사 난수열 생성에 응용되며, n>4인 페르마 소수의 존재 여부, 페르마 소수 및 합성수의 무한 존재 여부 등은 미해결 문제로 남아 있다.

2. 역사

피에르 드 페르마는 1637년에 2²ⁿ + 1 형태의 모든 정수가 소수일 것이라고 추측했지만, 1732년 레온하르트 오일러가 F₅ = 4,294,967,297 = 641 × 6,700,417 로 소인수분해하여 이 추측이 틀렸음을 보였다. 오일러는 페르마 수의 인수가 k2ⁿ⁺¹ + 1 형태를 가져야 한다는 것을 증명했으며(이후 루카스에 의해 k2ⁿ⁺² + 1 형태로 개선됨), 이는 페르마가 계산 실수로 인해 인수를 찾지 못한 이유를 설명해준다.

F₀부터 F₄까지는 소수임을 쉽게 확인할 수 있었으나, F₅ 이후의 수는 17세기 당시 기술로는 계산하기 어려웠고, 작은 소인수를 가지지 않아 페르마가 오류를 발견하기 어려웠다. 현재 n > 4 인 경우에 대해 알려진 페르마 소수는 없으며, 페르마 수에 대한 여러 가지 해결되지 않은 문제들이 남아있다.

2.1. 페르마의 추측과 오일러의 반증

피에르 드 페르마는 1637년에 2ⁿ + 1 형태 (n은 음이 아닌 정수)로 표현 가능한 모든 정수가 소수일 것이라고 추측했다. 그러나 1732년 레온하르트 오일러가 F₅ = 4,294,967,297 = 641 × 6,700,417 로 소인수분해하여 페르마의 추측이 틀렸음을 증명했다.

오일러는 F_n의 모든 인수가 k2ⁿ⁺¹ + 1 형태를 가져야 함을 증명했고 (이후 루카스에 의해 k2ⁿ⁺² + 1로 개선됨), 641이 F₅의 인수라는 것은 641 = 2⁷ × 5 + 1 및 641 = 2⁴ + 5⁴ 에서 유추할 수 있다.

페르마는 오일러가 증명한 인수 형식을 알고 있었을 가능성이 있지만, 간단한 계산을 수행하여 인수를 찾지 못한 것은 계산 실수 때문으로 추정된다.

F₀, ..., F₄는 쉽게 소수임을 확인할 수 있지만, F₅ 이후는 (17세기 당시의 계산 기술로는) 상당히 큰 수이며 작은 소인수를 포함하지 않아 페르마가 추측의 오류를 발견하기 어려웠다.

3. 성질

* 페르마 소수는 홀수 소수 p에 대해 두 개의 p 거듭제곱의 차로 표현될 수 없다.
* F₀와 F₁을 제외하고, 페르마 수의 마지막 십진수는 7이다.
* 모든 페르마 수의 역수의 합은 무리수이다. (1963년 솔로몬 W. 골롬)

페팽의 검사법은 n > 0에 대해 $F\_n=2^\{2^n\}+1$을 n번째 페르마 수라고 할 때, $F\_n$이 소수일 필요충분조건은 $3^\{(F\_n-1)/2\}\backslash equiv-1\backslash pmod\{F\_n\}$이다. $3^\{(F\_n-1)/2\}$ 식은 반복 제곱을 사용하여 $F\_n$을 모듈로 계산할 수 있으며, 이로 인해 검사법은 빠른 다항 시간 알고리즘이 된다. 하지만 페르마 수는 매우 빠르게 증가하므로, 합리적인 시간과 공간 내에서 소수의 페르마 수만 검사할 수 있다.

페르마 수의 약수와 같은 형태의 숫자 $k\backslash times2^m+1$의 소수성을 검사하는 방법으로 프로스 정리가 있다. 홀수 에 대해 $N\; =\; k\backslash times2^m\; +\; 1$이라고 할 때, 만약 $a^\{(N-1)/2\}\; \backslash equiv\; -1\backslash pmod\{N\}$를 만족하는 정수 a가 존재한다면 $N$은 소수이다. $N\; =\; F\_n\; >\; 3$이면, 야코비 기호는 $a\; =\; 3$에 대해 항상 −1과 같으며, 프로스 정리의 이 특수한 경우는 페팽의 검사법으로 알려져 있다.

페팽의 검사는 페르마 수의 소수성에 대한 필요충분조건을 제공하며, 현대 컴퓨터로 구현할 수 있다.

3.1. 기본 성질

페르마 수는 다음 점화 관계를 만족한다.

:$F\_n\; =\; (F\_\{n-1\}\; -\; 1)^2\; +\; 1$
:$F\_n\; =\; F\_0\; \backslash cdots\; F\_\{n-1\}\; +\; 2$
:(n ≥ 1)

:$F\_n\; =\; F\_\{n-1\}\; +\; 2^\{2^\{n-1\}\}F\_0\; \backslash cdots\; F\_\{n-2\}$
:$F\_n\; =\; F\_\{n-1\}^2\; -\; 2(F\_\{n-2\}\; -\; 1)^2$
:(n ≥ 2)

위 식들은 수학적 귀납법으로 증명할 수 있다. 두 번째 식으로부터 골드바흐의 정리를 추론할 수 있는데, 이는 서로 다른 두 페르마 수는 서로소라는 것이다.

F₀와 F₁을 제외한 모든 페르마 수의 일의 자리 숫자는 7이다.

모든 페르마 수의 역수의 합은 무리수이다. (솔로몬 W. 골롬, 1963)

페르마 수는 모두 홀수이므로, 위에서 제시된 네 번째 점화식으로부터 서로 다른 두 페르마 수는 서로소임을 알 수 있다.

페르마 수는 다음의 합동식을 만족한다.
* n ≥ 2 이면, $F\_n\; \backslash equiv\; 17\; \backslash \; or\; \backslash \; 41\; \backslash pmod\{72\}$
* n ≥ 2 이면, $F\_n\; \backslash equiv\; 17,\; 37,\; 57\; \backslash \; or\; \backslash \; 97\; \backslash pmod\{100\}$

$2^\{m\}\; +\; 1$ ($m$ ≥ 2) 형태의 소수는 페르마 수이다. 일반적으로, $a^\{m\}\; +\; 1$ ($a$ ≥ 2) 가 소수이면, $a$는 짝수이고 $m$은 2의 거듭제곱이다.

3.2. 소수성

2ⁿ + 1 꼴의 수가 소수라면 n은 반드시 2의 거듭제곱이어야 한다. 따라서 2ⁿ + 1 꼴의 소수는 모두 페르마 수가 된다. 이러한 소수를 페르마 소수라고 한다. 현재까지 알려진 페르마 소수는 F₀, F₁, F₂, F₃, F₄ 뿐이다. 어떤 수가 페르마 소수인지 확인할 때에는 페팽 소수판별법이 많이 쓰인다.

n > 4인 페르마 소수는 아직 알려져 있지 않다.

소수 정리에 따르면, N 주변의 적절한 구간 내의 임의의 정수가 소수일 확률은 1/ln N이다. 페르마 수가 크기가 같은 임의의 정수와 같은 확률로 소수이고, F₅, ..., F₃₂가 합성수라는 점을 이용하면, F₄ 이후의 페르마 소수의 예상 개수는 다음과 같이 추정할 수 있다.
:
이는 F₄ 이후의 페르마 소수가 존재할 확률의 상한으로 해석할 수 있다.

이 주장은 엄밀한 증명은 아니다. 페르마 수가 "무작위"로 행동한다고 가정하지만, 페르마 수의 인수에는 특별한 속성이 있기 때문이다. Boklan과 콘웨이는 또 다른 페르마 소수가 있을 확률이 10억 분의 1 미만임을 시사하는 보다 정밀한 분석을 발표했다.

$F\_n=2^\{2^n\}+1$을 n번째 페르마 수라고 할 때, 페팽의 검사법은 다음과 같다.

:$F\_n$이 소수일 필요충분조건은 $3^\{(F\_n-1)/2\}\backslash equiv-1\backslash pmod\{F\_n\}$이다.

$3^\{(F\_n-1)/2\}$ 식은 반복 제곱을 사용하여 $F\_n$을 모듈로 계산할 수 있다. 이로 인해 페팽의 검사법은 빠른 다항 시간 알고리즘이 된다. 하지만 페르마 수는 매우 빠르게 증가하므로, 합리적인 시간과 공간 내에서는 소수의 페르마 수만 검사할 수 있다.

페르마 수의 약수와 같은 형태의 숫자 $k\backslash times2^m+1$의 소수성을 검사하는 방법으로 프로스 정리가 있다.

:프로스 정리 (1878). 홀수 에 대해 $N\; =\; k\backslash times2^m\; +\; 1$이라고 하자. 만약 다음 조건을 만족하는 정수 a가 존재한다면
:: $a^\{(N-1)/2\}\; \backslash equiv\; -1\backslash pmod\{N\}$
:그렇다면 $N$은 소수이다. 반대로, 위의 합동식이 성립하지 않고,
:: $\backslash left(\backslash frac\{a\}\{N\}\backslash right)=-1$ (야코비 기호 참조)
:이라면 $N$은 합성수이다.

만약 $N\; =\; F\_n\; >\; 3$이면, 위의 야코비 기호는 $a\; =\; 3$에 대해 항상 −1과 같으며, 프로스 정리의 이 특수한 경우는 페팽의 검사법으로 알려져 있다. 페팽의 검사법과 프로스 정리는 일부 페르마 수의 합성수를 증명하기 위해 컴퓨터에서 구현되었지만, 두 검사법 모두 특정한 비자명 약수를 제공하지는 않는다. 실제로, $F\_\{20\}$과 $F\_\{24\}$에 대한 특정한 소인수는 알려져 있지 않다.

페르마 수의 크기 때문에 소인수분해하거나 소수임을 확인하는 것조차 어렵다. 페팽의 검사는 페르마 수의 소수성에 대한 필요충분조건을 제공하며, 현대 컴퓨터로 구현할 수 있다.

3.3. 소인수 분해

페르마 수의 크기 때문에 소인수분해를 하거나 소수인지 판별하는 것은 매우 어렵다. 에두아르 뤼카는 1878년에 n ≥ 2 일 때 페르마 수 $F\_n$의 모든 인수가 $k\backslash times2^\{n+2\}+1$의 형태를 갖는다는 것을 증명했다(프로스 수 참고).

처음 12개의 페르마 수의 소인수 분해는 다음과 같다.

3.3.1. 소수성 상태

n^영어 > 4인 페르마 소수는 아직 알려져 있지 않다. 그밖에도 다음과 같은 의문은 해결되지 않고 있다.

* n^영어 > 4인 F_n이 모두 합성수인가?
* 페르마 소수가 무한히 많은가?
* 합성수인 페르마 수가 무한히 많은가?

5 ≤ n ≤ 32 사이의 모든 F_n은 합성수라는 것이 밝혀졌다. 이 중 5 ≤ n ≤ 11 사이의 수만이 완전한 소인수분해가 구해져 있다.
페르마 수 F_n 에 대하여 현재의 소수성 상태는 아래 표와 같다.

4. 작도 가능한 정다각형과의 관계

카를 프리드리히 가우스는 정다각형의 작도 가능성에 대한 충분 조건을 공식화했고, 피에르 방첼이 1837년에 필요 조건에 대한 완전한 증명을 제시했다. 그 결과는 가우스-방첼 정리로 알려져 있다.

: n개의 변을 가진 정다각형은 n이 2의 거듭제곱이거나 2의 거듭제곱과 서로 다른 페르마 소수의 곱일 때, 즉 자(定規)와 컴퍼스로 작도할 수 있다. 여기서 k, s는 음이 아닌 정수이고 p_i는 서로 다른 페르마 소수이다.

양의 정수 n이 위의 형태를 갖는 것은 오일러 피 함수 φ(n)이 2의 거듭제곱일 때와 동치이다.

5. 일반화된 페르마 수

a^{영어2n영어} + b^{영어2n영어} 형태의 수를 일반화된 페르마 수라고 한다. 여기서 a, b는 서로소인 정수이고, a > b > 0이다. 홀수 소수 p가 일반화된 페르마 수가 되려면, p는 1 (mod 4)와 합동이어야 한다.

일반 페르마 수와 유사하게, a^{영어2n영어} + 1 형태의 일반화된 페르마 수는 F_n(a)로 표기한다. 예를 들어 100,000,001은 F₃(10)으로 표기한다. 이 형태의 소수 a^{영어2n영어} + 1을 "밑이 a인 페르마 소수"라고 부르며, a가 짝수일 경우에만 존재한다.

란다우의 네 번째 문제는 일반화된 페르마 소수 F_n(a)가 무한히 많은지 묻는다. 일반화된 페르마 소수는 소수임을 증명하기 쉽기 때문에 최근 수론 분야에서 연구 주제가 되고 있다.

일반화된 페르마 수는 짝수 a^영어에 대해서만 소수일 수 있다. a^영어가 홀수이면 모든 일반화된 페르마 수는 2로 나누어지기 때문이다. 홀수 밑에 대해 "반 일반화된 페르마 수"를 정의할 수 있는데, 밑이 a(홀수 a)인 반 일반화된 페르마 수는 $\backslash frac\{a^\{2^n\}\; \backslash !+\; 1\}\{2\}$ 이고, 각 홀수 밑에 대해 유한 개의 반 일반화된 페르마 소수가 있을 것으로 예상된다.

짝수 a^영어에 대한 일반화된 페르마 수($F\_n(a)$)는 $a^\{2^n\}\; \backslash !+\; 1$이고, 홀수 a^영어에 대해서는 $\backslash frac\{a^\{2^n\}\; \backslash !\backslash !+\; 1\}\{2\}$이다.

6. 응용

페르마 소수는 1부터 N (N은 2의 거듭제곱) 범위의 숫자 의사 난수열을 생성하는 데 유용하다. 일반적인 방법은 1과 P - 1 사이의 임의의 시드 값을 사용하는 것이다. 여기서 P는 페르마 소수이다. 이 값을 P의 제곱근보다 크고 P를 법 P에 대한 원시근(즉, 이차 잉여가 아닌) A와 곱한다. 그런 다음 결과에 대해 모듈로 P 연산을 수행한다. 그 결과는 RNG에 대한 새 값이다.

:$V\_\{j+1\}\; =\; (A\; \backslash times\; V\_j)\; \backslash bmod\; P$ (선형 합동 생성기 참조)

이는 대부분의 데이터 구조가 2^X개의 가능한 값을 가진 멤버를 가지므로 컴퓨터 과학에서 유용하다. 예를 들어, 바이트는 256(2⁸)개의 가능한 값(0–255)을 가진다. 따라서 바이트 또는 바이트들을 임의의 값으로 채우기 위해 1–256 값을 생성하는 난수 생성기를 사용할 수 있으며, 바이트는 출력 값 -1을 사용한다. 이 때문에 매우 큰 페르마 소수는 데이터 암호화에 특히 중요하게 사용될 수 있다. 이 방법은 P - 1 반복 후 시퀀스가 반복되므로 의사 난수 값만 생성한다. 잘못 선택된 승수는 시퀀스가 P - 1보다 일찍 반복될 수 있다.

7. 미해결 문제

* 인 페르마 소수는 아직 알려져 있지 않다. 그밖에도 다음과 같은 의문은 해결되지 않고 있다.
인 이 모두 합성수인가?
페르마 소수가 무한히 많은가?
** 합성수인 페르마 수가 무한히 많은가?
* 에 대해 이 합성수임이 알려져 있지만, 그 소인수는 하나도 알려져 있지 않다. 를 하나 정했을 때 이 을 나누는 현상이 무수히 일어나는지도 알려져 있지 않다.