페르마 수의 몇가지 성질?

정수론 수업을 듣다가 페르마 수에 대한 내용이 나왔는데 그냥 궁금해서 찾아봤다

대학교가 전체싸강으로 결정나서.. 공부하는데 나태해질까봐 글이라도 적어서 기억해보자는 느낌으로다가...

 

먼저 페르마 수란 $F_n = 2^{2^n} + 1$인 수를 의미한다.

페르마는 이 $F_n$은 모두 소수라고 어림짐작했는데 실제로는 $0\leq n\leq 4$인 $n$에 대해서는 소수가 맞지만

$n = 5$인 $F_5 = 2^{2^5} + 1 = 4294967297 = 641 \times 6700417$로 인수분해가 가능한 합성수라는것이 밝혀졌다.

 

페르마 수의 몇가지 기본 속성

속성 1) $1 \leq n$ 에 대해 $F_n = (F_{n-1}-1)^2+1$이 성립한다.

 

증명

$ \begin{align*}
(F_{n-1}-1)^2+1 &= (2^{2^{n-1}}+1-1)^2+1\\ 
 &= 2^{2^n}+1\\
 &= F_n\\
\end{align*} $

 

---

 

속성 2) $1 \leq n$ 에 대해 $F_n= F_0F_1\cdots F_{n-1}+2$이 성립한다.

 

증명

먼저 $F_n$과 $F_{n-1}$의 관계를 다음과 같이 볼 수 있다.

$\begin{align*}
F_n &= 2^{2^n}+1\\
 &= (2^{2^{n-1}})^2 + 2\times 2^{2^{n-1}}+1 - 2\times2^{2^{n-1}}\\
 &= (2^{2^{n-1}}+1)^2 - 2\times2^{2^{n-1}}\\
 &= (F_{n-1})^2-2(F_{n-1}-1)\\
 &= (F_{n-1}-2)F_{n-1}+2\\
\end{align*}$

 

이 관계식을 가지고 수학적 귀납법을 통해 증명하고자 한다.

먼저 $n=1$ 일 때,

$\begin{align*} 
F_1 &= (F_0-2)F_0+2\\
 &= (2^{2^0}+1-2)F_0+2\\
 &= F_0+2
\end{align*}$

 

$\therefore F_1-2 = F_0$

 

$n=2$ 일 때,

$\begin{align*}  
F_2 &= (F_1-2)F_1+2\\ 
 &= F_0F_1+2 \qquad\qquad\qquad (\because F_1-2=F_0)
\end{align*}$

 

$\therefore F_2-2 = F_0F_1$

 

$n=3$ 일 때,

$\begin{align*}  
F_3 &= (F_2-2)F_2+2\\ 
 &= F_0F_1F_2+2 \qquad\qquad\qquad (\because F_2-2=F_0F_1)\\
\end{align*}$

 

$\therefore F_3-2 = F_0F_1F_2$

 

$n=i$ 일 때,

$\begin{align*}   
F_i &= (F_{i-1}-2)F_{i-1}+2\\  
 &= F_0F_1F_2 \cdots F_{i-1} + 2 \qquad\qquad\qquad (\because F_{i-1}-2=F_0F_1F_2 \cdots F_{i-2})
\end{align*}$

 

$\therefore F_i-2 = F_0F_1F_2 \cdots F_{i-1}$

 

따라서 수학적 귀납법에 따라

모든 $n$ 에 대하여

$F_n=(F_{n-1}-2)F_{n-1}+2=F_0F_1F_2 \cdots F_{n-1}+2$를 만족하게 된다.

 

다른 방법

$F_0F_1F_2...F_{n-1}=F_n-2$라고 가정을 했을 때, $n=0$일 때는 $F_0=3$이고 $F_1=5$로 성립한다.

 

따라서 

$\begin{align*}    
F_0F_1F_2...F_{n-1}F_n &= (F_0F_1F_2...F_{n-1})F_n\\
 &= (F_n-2)F_n = (2^{2^n}-1)(2^{2^n}+1)\\
 &= (2^{2^n})^2-1=2^{2^{n+1}}-1=F_{n+1}-2\\
\end{align*}$

 

로 증명을 할 수 있다.

---

속성 3) $n\neq m$일 때 $gcd(F_n, F_m)=1$이다.

 

$m < n$에 대해 $F_n$과 $F_m$을 나누는 최대 공약수를 $d$라고 하자.

그럼 이글 속성 2에서 증명한 성질때문에

$F_n-F_0F_1F_2...F_{n-1} = 2$이고 

$d | (F_n - F_0F_1F_2...F_m...F_{n-1})= 2$가 된다.

위의 식을 성립하기 위해서는 $d = 1$이거나 $d=2$여야 하는데 페르마수는 전부 홀수기 때문에 $d=2$가 될 수 없다.

따라서 $d = 1$이 된다.

 

여기서 새롭게 알 수 있는점은 $d = 1$이므로 $n \neq m$에 대해 페르마수 $F_n$과 $F_m$은 서로소관계이고 서로 다른 소수의 곱으로 이루어져 있다. 즉 서로다른 두 페르마 수가 서로소라는 점은  소수가 무한히 많다는 것을 의미하기도 한다.