페미위키:포크 프로젝트/리브레 위키/페르마 수

정의

페르마 수(Fermat number)는

$F_n=2^{2^n}+1(n\ge 0)$

꼴인 정수를 뜻한다.

페르마 소수

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

“

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

“

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

$F_0=2^0+1=3$

$F_1=2^2+1=5$

$F_2=2^4+1=17$

$F_3=2^8+1=257$

$F_4=2^{16}+1=65537$

는 모두 소수이다. 그러나

$F_5=2^{32}+1=4294967297=641\cdot 6700417$

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

$F_6=2^{64}+1=274177\cdot 67280421310721$

$F_7=2^{128}+1=59649589127497217\cdot 57046889200685129054721$

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

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

성질

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

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

기본 성질

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

약수 관련 성질

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

정다각형 작도

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

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

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

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

페르마 수의 소인수분해

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

2021년 11월 1일까지 발견된 소인수는 359개이다. 소인수가 새로 발견되면 이 페이지에서 소식이 업데이트 된다. 구체적인 현황은 아래와 같다.

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

같이 보기

• 메르센 소수
• 피어폰트 소수
• 프로트 소수

외부 링크

• Distributed Search for Fermat Number Divisors