피보나치 소수

피보나치 소수(Fibonacci prime)는 피보나치 수열의 항 중 소수인 수들을 가리킨다.

처음 10개 피보나치 소수는 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, …이다.

피보나치 수열의 소수 번째 항

이 문서에서는 [math]\displaystyle{ F_n=\frac{\varphi^n-(-\varphi)^{-n}}{\sqrt{5}}, \varphi=\frac{1+\sqrt{5}}{2} }[/math]로 정의되는 수열을 기준으로 항 번호를 다룬다. 아래 성질들은 메르센 소수 문서에 서술된 정리들과 형태가 비슷하다.

• 기본 필요조건: [math]\displaystyle{ F_n }[/math]이 소수이려면 [math]\displaystyle{ n }[/math]이 4이거나 소수여야 한다.
• 증명: [math]\displaystyle{ n }[/math]이 4보다 크고 소수가 아니면 [math]\displaystyle{ n=ab, 2 \leq a \lt b \lt n }[/math]인 약수 [math]\displaystyle{ a, b }[/math]가 존재한다. 한편 피보나치 수의 성질인 [math]\displaystyle{ F_{u+v}=F_{u-1}F_v+F_uF_{v+1} }[/math]에서 [math]\displaystyle{ u=kb, v=b }[/math]라 하면 [math]\displaystyle{ F_{(k+1)b}=F_{kb-1}F_b+F_{kb}F_{b+1} }[/math]이고, 이에 따라 [math]\displaystyle{ F_b \mid F_{kb} \Rightarrow F_a \mid F_{(k+1)b} (k \geq 1) }[/math]이다. [math]\displaystyle{ k=1 }[/math]일 때 [math]\displaystyle{ F_b \mid F_b }[/math]는 자명하므로, 수학적 귀납법에 의해 [math]\displaystyle{ k=a:\ F_b \mid F_{ab}=F_n }[/math]임을 알 수 있다. 한편 [math]\displaystyle{ 3 \leq b \lt n }[/math]이므로 [math]\displaystyle{ 2 \leq F_b \lt F_n }[/math]이며, [math]\displaystyle{ F_n }[/math]은 소수가 될 수 없다.

위 성질은 메르센 수 [math]\displaystyle{ M_n=2^n-1 }[/math]이 소수이려면 지수도 소수여야 한다는 점과 비슷하다. 하지만 명제의 역은 성립하지 않는다. 즉 [math]\displaystyle{ n }[/math]이 소수여도 [math]\displaystyle{ F_n }[/math]도 소수라 할 수는 없고, 반례 중 가장 작은 수는 [math]\displaystyle{ F_{19}=4181=37 \cdot 113 }[/math]이다.

또한 [math]\displaystyle{ \gcd(F_m, F_n)=F_{\gcd(m, n)} }[/math] 관계식도 성립하며, 메르센 수에서 [math]\displaystyle{ \gcd(M_m, M_n)=M_{\gcd(m, n)} }[/math]인 점과 흡사하다.

약수 관련 성질

이 문단에서 [math]\displaystyle{ a+b \sqrt{5} \equiv c+d \sqrt{5} \pmod q }[/math]라 적힌 식은 [math]\displaystyle{ a \equiv c, b \equiv d \pmod q }[/math]를 의미하며, 나눗셈은 모듈러 역수를 곱하는 것으로 간주한다.

• 성질 ①: [math]\displaystyle{ n }[/math]이 홀수일 때, [math]\displaystyle{ F_n }[/math]의 홀수 약수를 4로 나눈 나머지는 1이다. 즉 모든 홀수 소인수는 피타고라스 소수이다.
• 증명: 피보나치 수의 성질 [math]\displaystyle{ F_{u+v}=F_{u-1}F_v+F_uF_{v+1} }[/math]에서 [math]\displaystyle{ u=v+1, n=2v+1 }[/math]을 대입하면 [math]\displaystyle{ F_n=F_v^2+F_{v+1}^2 }[/math]이다. 또한 [math]\displaystyle{ F_n }[/math]의 소인수 [math]\displaystyle{ q }[/math] 에 대해 [math]\displaystyle{ F_v^2 \equiv -F_{v+1}^2 \pmod q }[/math]이다. 이때 [math]\displaystyle{ F_v, F_{v+1} }[/math]은 서로 이웃한 피보나치 수이므로 서로소이다. 즉 [math]\displaystyle{ xF_{v+1} \equiv 1 \pmod q }[/math]인 모듈러 역수 [math]\displaystyle{ x }[/math]가 존재하고, 이를 대입하면 [math]\displaystyle{ (xF_v)^2 \equiv -1 \pmod q }[/math]가 된다. 따라서 -1은 법 [math]\displaystyle{ q }[/math]에 대한 이차잉여이며, 홀수 [math]\displaystyle{ q }[/math]는 [math]\displaystyle{ 4m+1 }[/math] 꼴의 소수이다.
• 성질 ②: [math]\displaystyle{ p }[/math]가 소수일 때, [math]\displaystyle{ q \mid F_p }[/math]인 소인수 [math]\displaystyle{ q }[/math]가 있다. 이때 [math]\displaystyle{ q \equiv \pm 1 \pmod 5 }[/math]이면 [math]\displaystyle{ q=4kp+1 }[/math], [math]\displaystyle{ q \equiv \pm 2 \pmod 5 }[/math]이면 [math]\displaystyle{ q=(4k-2)p-1 }[/math] 꼴로 표현된다. (단, [math]\displaystyle{ k }[/math]는 자연수)
  • 보조정리: [math]\displaystyle{ q }[/math]가 소수일 때, [math]\displaystyle{ q \mid F_{q-\delta}, \delta=\left(\frac{q}{5} \right) }[/math]. 여기서 괄호 표시는 르장드르 기호이다.
  • 보조정리 증명: [math]\displaystyle{ 2\varphi=1+\sqrt{5} }[/math]에서 [math]\displaystyle{ (2\varphi)^q \equiv (1+\sqrt{5})^q \equiv 1+5^{\frac{q-1}{2}}\sqrt{5} \pmod q }[/math]이다. 여기서 페르마의 소정리 및 오일러의 규준에 의해 [math]\displaystyle{ 2\varphi^q \equiv 1+\delta\sqrt{5} }[/math]이다. [math]\displaystyle{ \delta=1 }[/math]이면 [math]\displaystyle{ 2\varphi^q \equiv 2\varphi, \varphi^{q-1} \equiv (-\varphi)^{-(q-1)} \equiv 1 \pmod q }[/math]이고, [math]\displaystyle{ \varphi^{q-1}-(-\varphi)^{-(q-1)} \equiv 0, F_{q-1} \equiv 0 \pmod q }[/math]이다. [math]\displaystyle{ \delta=-1 }[/math]이면 [math]\displaystyle{ 2\varphi^q \equiv -2\varphi^{-1}, \varphi^{q+1} \equiv (-\varphi)^{-(q+1)} \equiv -1 \pmod q }[/math]이며 [math]\displaystyle{ \varphi^{q+1}-(-\varphi)^{-(q+1)} \equiv 0, F_{q+1} \equiv 0 \pmod q }[/math]가 성립한다. 이 두 경우는 [math]\displaystyle{ F_{q-\delta} \equiv 0 \pmod q }[/math]로 묶어 쓸 수 있다.
• 증명: [math]\displaystyle{ q \mid F_p }[/math]이면 보조정리에 의해 [math]\displaystyle{ q \mid \gcd(F_p, F_{q-\delta})=F_{\gcd(p, q-\delta)} }[/math]이다. 만약 [math]\displaystyle{ p \nmid q-\delta }[/math]이면 [math]\displaystyle{ p }[/math]는 소수이므로 [math]\displaystyle{ \gcd(p, q-\delta)=1, q \mid F_1=1 }[/math]이지만 이는 [math]\displaystyle{ q }[/math]가 소수라는 전제와 모순이다. 그러므로 [math]\displaystyle{ p \mid q-\delta, q=mp+\delta }[/math]이다. [math]\displaystyle{ q \equiv \pm 1 \pmod 5, \delta=1 }[/math]이면 [math]\displaystyle{ q=mp+1 }[/math]이며, 4로 나눈 나머지가 1이려면 [math]\displaystyle{ q=4kp+1 }[/math]이다. [math]\displaystyle{ q \equiv \pm 2 \pmod 5, \delta=-1 }[/math]이면 [math]\displaystyle{ q=mp-1 }[/math]이며, 같은 방법으로 [math]\displaystyle{ q=(4k-2)p-1 }[/math]을 유도할 수 있다.
• 성질 ③: 어떤 소수 [math]\displaystyle{ p }[/math]의 일의 자리가 7 또는 9이고 [math]\displaystyle{ q=2p-1 }[/math]도 소수이면 [math]\displaystyle{ q \mid F_p }[/math]이다.
• 증명: [math]\displaystyle{ p \equiv 7 \text{ or } 9 \pmod{10} }[/math]이면 [math]\displaystyle{ p \equiv 13 \text{ or } 17 \pmod{20} }[/math]이며, [math]\displaystyle{ \left(\frac{5}{q}\right) = -1 }[/math]이다. [math]\displaystyle{ (\sqrt{5})^q \equiv 5^{\frac{q-1}{2}}\sqrt{5} \equiv -\sqrt{5}, \pmod q }[/math]를 이용하면 [math]\displaystyle{ \left(\frac{1+\sqrt{5}}{2} \right)^q \equiv \frac{1-\sqrt{5}}{2} \pmod q }[/math]이므로 [math]\displaystyle{ \varphi^q \equiv -\varphi^{-1}, \varphi^{q+1} \equiv -1 \pmod q }[/math]이다. 따라서 [math]\displaystyle{ \varphi^{2p} \equiv -1, \varphi^p \equiv (-\varphi)^{-p} \pmod q }[/math]이고, 정리하면 [math]\displaystyle{ F_p \equiv 0 \pmod q }[/math]가 된다.
• 예: [math]\displaystyle{ 37 \mid F_{19}, 73 \mid F_{37}, 157 \mid F_{79} }[/math]

알려진 피보나치 소수

피보나치 소수는 무한 개 존재할 것으로 추정하고 있지만 증명되지는 않았다. 2022년 7월 22일까지 알려진 피보나치 소수는 36개이며, 그 뒤로 유력 소수 15개가 더 있다.

[math]\displaystyle{ F_n }[/math]이 소수인 항 번호를 나열하면 아래와 같다.

• 소수: 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 37511, 50833, 81839, 104911, 130021, 148091
• 유력 소수: 201107, 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369, 3340367