페르마 수

정의

페르마 수(Fermat number)는

[math]\displaystyle{ F_n = 2^{2^n}+1\quad (n\ge 0) }[/math]

꼴인 정수를 뜻한다.

페르마 소수

페르마 소수(Fermat prime)는 페르마 수 중 소수인 수를 말한다. 피에르 드 페르마는

“

모든 페르마 수는 소수이다.

“

라는 추측을 제시했다. 실제로 처음 다섯 페르마 수

[math]\displaystyle{ F_0=2^0+1=3 }[/math]

[math]\displaystyle{ F_1=2^2+1=5 }[/math]

[math]\displaystyle{ F_2=2^4+1=17 }[/math]

[math]\displaystyle{ F_3=2^8+1=257 }[/math]

[math]\displaystyle{ F_4=2^{16}+1=65537 }[/math]

는 모두 소수이다. 그러나

[math]\displaystyle{ F_5=2^{32}+1=4294967297=641\cdot 6700417 }[/math]

임을 레온하르트 오일러가 1732년에 발견해 참이 아닌 것으로 밝혀졌다. 이후 [math]\displaystyle{ F_4 }[/math]보다 큰 페르마 소수는 2021년 현재 발견되지 않았다.

[math]\displaystyle{ F_6=2^{64}+1=274177\cdot 67280421310721 }[/math]

[math]\displaystyle{ F_7=2^{128}+1=59649589127497217\cdot 57046889200685129054721 }[/math]

페르마 수의 소수 여부를 가려내는 방법으로 페팽 소수판정법이 있다. [math]\displaystyle{ F_n }[/math]이 소수이면 합동식 [math]\displaystyle{ 3^{\frac{F_n-1}{2}} \equiv -1 \pmod{F_n} }[/math]을 만족하고, 그 역도 성립한다. 증명 및 자세한 내용은 해당 문서 참조. 물론 어떤 페르마 수의 소인수가 이미 발견된 상태라면 별도의 판정법이 필요하지는 않다.

[math]\displaystyle{ F_5 }[/math]가 합성수임을 알아낸 것을 시작으로 [math]\displaystyle{ F_6,F_7,F_8,\cdots }[/math] 등도 약수가 속속 발견되었다. [math]\displaystyle{ 5 \le n \le 32 }[/math] 범위에서는 모두 합성수이고, 2021년 11월까지 합성수임이 판명 난 페르마 수는 316개이다. 페르마는 초기에 "모든 페르마 수는 소수"라는 추측을 했었지만 현재는 반대로 "[math]\displaystyle{ n \ge 5 }[/math]에서는 페르마 소수가 존재하지 않는다"와 같이 증명 목표를 뒤집어서 접근하고 있다. 물론 정말 페르마 소수는 더 이상 없는지, 혹은 있더라도 유한 개인지는 아직까지 밝혀지지 않았다.

성질

• [math]\displaystyle{ N=2^n+1 }[/math]이 소수이면 [math]\displaystyle{ n=2^k\ (k \ge 0) }[/math] 꼴이다.
  • 증명: 임의의 자연수는 적당한 홀수 [math]\displaystyle{ a }[/math]가 존재하여 [math]\displaystyle{ n=a \cdot 2^{k}\ (k\ge 0) }[/math] 형태로 쓸 수 있다. 여기서 [math]\displaystyle{ a \ge 3 }[/math]이라고 가정하자. [math]\displaystyle{ 2^{2^k}=x }[/math]로 치환하면 [math]\displaystyle{ N=2^{2^k \cdot a}+1 = x^a+1 }[/math]로 쓸 수 있으며, 이 식을 인수분해하면 [math]\displaystyle{ N=(x+1)(x^{a-1}-x^{a-2}+ \cdots -x+1) }[/math]이므로 [math]\displaystyle{ x+1 \mid N }[/math]이다. 이때 [math]\displaystyle{ x+1 = 2^{2^k}+1 \ge 3,\ x+1\lt N }[/math]이므로 [math]\displaystyle{ N }[/math]은 소수가 아니다. 따라서 홀수 [math]\displaystyle{ a }[/math]는 3 이상이 될 수 없으며, [math]\displaystyle{ n }[/math]은 2 이외의 소인수를 가지지 않는다.

페르마 수와 비슷한 모양을 한 메르센 수 [math]\displaystyle{ M_n=2^n-1 }[/math]의 경우 [math]\displaystyle{ M_n }[/math]이 소수이기 위한 필요조건은 [math]\displaystyle{ n }[/math]이 소수라는 것이다. 부호를 바꿔서 [math]\displaystyle{ 2^n+1 }[/math]이 소수가 되려면 지수가 2의 거듭제곱이 되어야 하며, 페르마 수와 페르마 소수는 이 전제에 따라 위와 같이 정의된 것이다.

기본 성질

1. [math]\displaystyle{ F_0F_1F_2\cdots F_{n-1}=F_n - 2 }[/math]
   • 증명: 먼저 [math]\displaystyle{ n=1 }[/math]일 때 [math]\displaystyle{ F_0 = F_1-2 = 3 }[/math]으로, 주어진 관계식은 참이다. 이어서 [math]\displaystyle{ n=k (k \ge 1) }[/math]일 때 참이라고 가정하면 [math]\displaystyle{ \displaystyle F_{k+1}-2 = 2^{2^{k+1}}-1 = (2^{2^k}-1)(2^{2^k}+1) = (F_{k}-2)F_{k} }[/math]이고, 여기에 위 관계식을 대입한다. [math]\displaystyle{ \displaystyle F_{k+1}-2 = (F_0F_1F_2\cdots F_{k-1})\cdot F_{k} = F_0F_1F_2\cdots F_{k} }[/math] 따라서 [math]\displaystyle{ n=k+1 }[/math]일 때도 식은 성립한다. 수학적 귀납법에 따라 원 등식은 참이다.
2. 서로 다른 정수 [math]\displaystyle{ m,n }[/math]에 대해 [math]\displaystyle{ \gcd(F_m,F_n)=1 }[/math]이다.
   • 증명: 일반성을 잃지 않고 [math]\displaystyle{ m\lt n }[/math]이라 두고 위 성질을 가져온다. [math]\displaystyle{ \displaystyle F_n - 2 = F_0F_1F_2\cdots F_{n-1} }[/math]에서 우변에 [math]\displaystyle{ F_m }[/math] 항이 들어가 있으므로 [math]\displaystyle{ F_m \mid F_n - 2 }[/math]이다. 그러면 [math]\displaystyle{ F_m }[/math]의 약수 [math]\displaystyle{ q(\gt 1) }[/math]에 대해 [math]\displaystyle{ q \mid F_n - 2 }[/math]가 성립한다. 그런데 페르마 수는 홀수이기에 약수는 무조건 홀수이고, [math]\displaystyle{ q \ge 3 }[/math]이어야 한다. 따라서 [math]\displaystyle{ q \nmid F_n }[/math]이고, [math]\displaystyle{ F_m,F_n }[/math]의 공약수는 1 외에는 존재하지 않는다. 따라서 서로 다른 페르마 수는 서로소이다.
3. [math]\displaystyle{ n \ge 2 }[/math]일 때, [math]\displaystyle{ F_n }[/math]을 120으로 나눈 나머지는 17이다.
   • 증명: [math]\displaystyle{ 2^8 \equiv 2^4 \pmod 120 }[/math]이므로, 자연수 [math]\displaystyle{ k }[/math]에 대해 [math]\displaystyle{ 2^{4k} \equiv 16 \pmod{120} }[/math]이다. 한편 2 이상의 [math]\displaystyle{ n }[/math]에 대해 [math]\displaystyle{ F_n = 2^{2^n}+1 = 2^{4k}+1 }[/math] 꼴로 나타낼 수 있으며, [math]\displaystyle{ F_n \equiv 17 \pmod{120} }[/math]이 성립한다.
   • 따라서 17 이상의 페르마 수를 십진법으로 쓰면 일의 자리수는 항상 7이다.

약수 관련 성질

1. 페르마 수 [math]\displaystyle{ F_n }[/math]의 약수는 항상 [math]\displaystyle{ k\cdot 2^{n+1}+1 }[/math]의 형태이다.
   • 증명: [math]\displaystyle{ q\mid F_n }[/math]인 소인수 [math]\displaystyle{ q }[/math]를 가정하자. 그러면 (★) [math]\displaystyle{ 2^{2^n} \equiv -1 \pmod q }[/math]이고, 양변을 제곱하면 [math]\displaystyle{ 2^{2^{n+1}} \equiv 1 \pmod q }[/math]이다. 한편 페르마의 소정리에 의해 [math]\displaystyle{ 2^{q-1} \equiv 1 \pmod q }[/math]도 성립한다. 즉 [math]\displaystyle{ q\mid 2^{q-1}-1,\ q\mid 2^{2^{n+1}}-1 }[/math]이고, 따라서 [math]\displaystyle{ q\mid \gcd(2^{2^{n+1}}-1, 2^{q-1}-1) }[/math]이다. 유클리드 호제법으로 최대공약수를 다시 쓰면 [math]\displaystyle{ q \mid 2^{\gcd(2^{n+1},q-1)}-1 }[/math]이다. 이때 [math]\displaystyle{ 2^{n+1} }[/math]의 약수는 항상 2의 거듭제곱이므로 [math]\displaystyle{ \gcd(2^{n+1},q-1) = 2^m (m\le n+1) }[/math] 꼴로 써진다. 만약 [math]\displaystyle{ m\le n }[/math]이라면, [math]\displaystyle{ q \mid 2^{2^m}-1 }[/math]이므로 [math]\displaystyle{ 2^{2^m} \equiv 1 \pmod q }[/math]이다. 여기서 양 변을 제곱할 때마다 좌변의 지수의 지수가 1씩 올라가서 [math]\displaystyle{ 2^{2^n} \equiv 1 \pmod q }[/math]에 도달한다. 하지만 이는 방금 전 (★) 식과 모순이다. 따라서 [math]\displaystyle{ m=n+1 }[/math]이어야 하고, [math]\displaystyle{ \gcd(2^{n+1},q-1) = 2^{n+1} }[/math] 즉 [math]\displaystyle{ 2^{n+1} \mid q-1,\ q \equiv 1 \pmod{2^{n+1}} }[/math]이다. 임의의 약수 역시 이 성질을 만족하는 소인수들의 곱이므로 마찬가지로 성립한다.
   • 여기까지가 레온하르트 오일러가 이끌어낸 성질이다. 실제로 그는 이 정리를 이용하여 [math]\displaystyle{ F_5 }[/math]의 약수를 구할 수 있었다. 구체적으로는 [math]\displaystyle{ q\equiv 1 \pmod {2^6} }[/math]을 만족하는 소수들을 나열하면 [math]\displaystyle{ q \in \{193, 257, 449, 577, 641, \cdots \} }[/math]이다. 이들 수로 차례대로 직접 나눠본 결과 약수 641을 찾았고, 나눈 몫인 6700417이 소수라는 사실도 이 방법으로 밝혀냈다.
2. [math]\displaystyle{ n \ge 2 }[/math]일 때, 페르마 수 [math]\displaystyle{ F_n }[/math]의 약수는 항상 [math]\displaystyle{ k\cdot 2^{n+2}+1 }[/math]의 형태이다.
   • 이 정리는 에두아르 뤼카가 증명한 것으로, 바로 위 오일러의 정리의 강화판이라 할 수 있다.
   • 증명: [math]\displaystyle{ q }[/math]를 [math]\displaystyle{ F_n }[/math]의 소인수라 하자. [math]\displaystyle{ 2^{2^n}+1 \equiv 0 \pmod q }[/math]에서 양 변에 [math]\displaystyle{ 2\cdot 2^{2^{n-1}} }[/math]을 더한다. 그러면 [math]\displaystyle{ \left(2^{2^{n-1}}+1 \right)^2 \equiv 2\cdot 2^{2^{n-1}} \pmod q }[/math]이며, [math]\displaystyle{ x=2^{2^{n-2}} }[/math]라 하면 [math]\displaystyle{ F_{n-1}^2 \equiv 2x^2 \pmod q }[/math]과 같이 쓸 수 있다. 이때 [math]\displaystyle{ \gcd(x,q)=1 }[/math]이므로 [math]\displaystyle{ xy \equiv 1 \pmod q }[/math]인 [math]\displaystyle{ y }[/math]가 존재한다. 이전 식의 양 변에 [math]\displaystyle{ y^2 }[/math]을 곱하면 [math]\displaystyle{ y^2 F_{n-1}^2 \equiv 2 \pmod q }[/math]가 된다. 이어 [math]\displaystyle{ a = y F_{n-1} \mod q }[/math]라 하면 [math]\displaystyle{ a^2 \equiv 2 \pmod q }[/math]와 같이 써진다. 이 식을 [math]\displaystyle{ 2^{2^n} \equiv -1 \pmod q }[/math]에 대입하면 [math]\displaystyle{ a^{2^{n+1}} \equiv -1 \pmod q }[/math]이고, 양 변을 제곱하면 [math]\displaystyle{ a^{2^{n+2}} \equiv 1 \pmod q }[/math]이다. 한편 위 기본 성질에 의해 [math]\displaystyle{ \gcd(F_{n-1},F_{n})=1 }[/math]이므로 [math]\displaystyle{ \gcd(F_{n-1},q)=1 }[/math]이고, [math]\displaystyle{ y,q }[/math] 끼리도 서로소이므로 [math]\displaystyle{ a,q }[/math] 역시 서로소이다. 그러므로 페르마의 소정리에 따라 [math]\displaystyle{ a^{q-1} \equiv 1 \pmod q }[/math]이다. 그 다음 단계는 바로 위의 정리와 같은 방법으로 접근하여 [math]\displaystyle{ 2^{n+2} \mid q-1,\ q \equiv 1 \pmod{2^{n+2}} }[/math]임을 알 수 있다.

정다각형 작도

• 자세한 내용은 작도 가능한 정다각형 문서 참조.

눈금 없는 자와 컴퍼스만을 이용하여 작도할 수 있는 정다각형의 조건은 페르마 소수와 관련이 있다. 정N각형이 작도 가능하려면 [math]\displaystyle{ \varphi(N)=2^{n} }[/math], 즉 N의 오일러 피 함수 값은 2의 거듭제곱이 되어야 한다.

• [math]\displaystyle{ \varphi(N)=2^{n} }[/math]이면 [math]\displaystyle{ N=2^{m}p_1p_2\cdots p_k }[/math] 꼴이다. 여기서 [math]\displaystyle{ p_j }[/math]는 서로 다른 페르마 소수이다.
  • 보조정리: 소수 [math]\displaystyle{ p }[/math]가 페르마 소수이면 [math]\displaystyle{ \varphi(p)=2^{n}\ (n \ge 1) }[/math]을 만족하고, 그 역도 성립한다.
  • 보조정리의 증명: 소수의 오일러 피 함수 값은 [math]\displaystyle{ \varphi(p)=p-1 }[/math]이다. [math]\displaystyle{ p=2^{2^{\ell}}+1 }[/math]이 페르마 소수이면 [math]\displaystyle{ \varphi(p)=2^{2^{\ell}} }[/math]이므로 2의 거듭제곱이 된다. 역으로, [math]\displaystyle{ \varphi(p)=2^n }[/math]을 만족하는 소수에 대해 [math]\displaystyle{ p=2^n+1 }[/math] 형태이다. 위의 '기본 성질'에 의해 [math]\displaystyle{ 2^n+1 }[/math]이 소수가 되려면 [math]\displaystyle{ n=2^{\ell} }[/math] 꼴이 되어야 하며, 이는 곧 [math]\displaystyle{ p }[/math]는 페르마 소수임을 뜻한다.
  • 보조정리에 따라 위 명제의 역이 성립함을 알 수 있고, 증명은 [math]\displaystyle{ \gcd(a,b)=1 \Rightarrow \varphi(ab)=\varphi(a)\varphi(b) }[/math]를 이용하면 된다.
  • 증명: [math]\displaystyle{ N=2^{m}p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k} }[/math]로 소인수분해가 된다고 하자. 여기서 [math]\displaystyle{ p_j(1 \le j \le k) }[/math]는 서로 다른 홀수 소수이다. 그러면 [math]\displaystyle{ \displaystyle \varphi(N)=\varphi(2^m) \prod_{j=1}^k {\varphi(p_j^{r_j})} = 2^{m-1} \prod_{j=1}^k {(p_j-1)p_j^{r_j-1}} }[/math]이다. 이때 가정에서 [math]\displaystyle{ \varphi(N) }[/math]이 오직 2만을 소인수로 가진다고 했으므로, [math]\displaystyle{ (p_j-1)p_j^{r_j-1} }[/math]항은 모두 1이거나 2의 거듭제곱이 되어야 한다. [math]\displaystyle{ p_j^{r_j-1} }[/math] 항은 밑이 홀수 소수라고 가정했으므로 [math]\displaystyle{ r_j=1 }[/math]이어야 한다. 또, [math]\displaystyle{ p_j-1 \ge 2 }[/math]이므로 [math]\displaystyle{ p_j-1 = 2^{n_j} }[/math] 형태여야 한다. 보조정리에 따라 이 조건을 만족하는 소수 [math]\displaystyle{ p_j }[/math]는 페르마 소수이고, [math]\displaystyle{ N=2^{m}p_1p_2\cdots p_k }[/math]가 된다.

따라서 변이 홀수인 정다각형이 작도 가능하려면 서로 다른 페르마 소수의 곱이 되어야 한다.

페르마 수의 소인수분해

이 페이지에서 각 페르마 수의 소인수 목록을 볼 수 있다.

2021년 11월 27일까지 합성수로 판명난 수는 316개, 발견된 소인수는 360개이다. 소인수가 새로 발견되면 이 페이지에서 소식이 업데이트 된다. 구체적인 현황은 아래와 같다.

• [math]\displaystyle{ 5 \le n \le 11 }[/math]: 소인수분해 완료. 각 소인수의 십진법 표현은 여기의 2~3쪽에 적혀 있다.
• [math]\displaystyle{ n=12 }[/math]: 현재까지 소인수 6개가 알려졌고, 여인수(cofactor)는 합성수이다.
• [math]\displaystyle{ n=13 }[/math]: 현재까지 소인수 4개가 알려졌고, 여인수는 합성수이다.
• [math]\displaystyle{ n \in \{15, 19, 25, 52, 287\} }[/math]: 현재까지 소인수 3개가 알려졌다. [math]\displaystyle{ F_{15},F_{19} }[/math]의 여인수는 합성수이고, 나머지 세 경우는 여인수의 소수 여부를 모른다.
• [math]\displaystyle{ n \in \{16, 17, 18, 27, 30, 36, 38, 39, 42, 77, 147, 150, 284, 416, 417\} }[/math]: 현재까지 소인수 2개가 알려졌다. [math]\displaystyle{ F_{16}, F_{17}, F_{18} }[/math]의 여인수는 합성수이고, 나머지 수들은 여인수의 소수 여부를 모른다.
• [math]\displaystyle{ n \in \{14, 21, 22, 23, 26, 28, 29, 31, 32, 37, 40\} }[/math]: 현재까지 소인수 하나가 알려졌다. [math]\displaystyle{ F_{14}, F_{21}, F_{22}, F_{23} }[/math]의 여인수는 합성수이고, 나머지 수들은 여인수의 소수 여부를 모른다.
• [math]\displaystyle{ n=20\ \text{or}\ 24 }[/math]: 페팽 소수판정법에 의해 합성수라는 사실은 알고 있지만 소인수는 아직까지 발견되지 않았다.
• [math]\displaystyle{ n \in \{33, 34, 35, 41, 44, 45, 46, 47, 49, 50, 51,\cdots \} }[/math]: 해당 수가 소수인지는 아직 모른다.
• 그 외 [math]\displaystyle{ n \ge 43 }[/math] 범위에서 소인수가 하나 알려진 페르마 수 274개가 있다.

같이 보기

• 페팽 소수판정법
• 메르센 소수
• 피어폰트 소수
• 프로트 소수

외부 링크

• Distributed Search for Fermat Number Divisors