Số Fermat

số nguyên tố Fermat
Đặt tên theo	Pierre de Fermat
Số các phần tử đã biết	5
Giả thuyết số phần tử	5
Dãy con của	số Fermat
Các phần tử đầu tiên	3, 5, 17, 257, 65537
Phần tử lớn nhất đã được biết	65537
Chỉ số OEIS	A019434

Số Fermat là một khái niệm trong toán học, mang tên nhà toán học Pháp Pierre de Fermat, người đầu tiên đưa ra khái niệm này. Nó là một số nguyên dương có dạng

F_{n}=2^{2^{n}}+1

.

với n là số nguyên không âm. Nếu một số Fermat là một số nguyên tố thì nó được gọi là số nguyên tố Fermat.

Tính chất cơ bản

Số Fermat thỏa mãn các hệ thức truy hồi sau

$F_{n}=(F_{n}-1)^{2}+1$

$F_{n}=F_{0}..F_{n-1}+2$

,với $n\geq 1$ , và

$F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}..F_{n-2}$

$F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}$

với $n\geq 2$ . Mỗi hệ thức trên có thể chứng minh bằng phương pháp quy nạp. Trong đó từ hệ thức thứ hai ta có thể suy ra Giả thuyết Goldbach rằng không có 2 số Fermat phân biệt mà ước chung của chúng lớn hơn 1. Để kiểm tra điều này, giả sử 0 ≤ i < j và F_i với F_j có chung 1 ước số a > 1. Khi đó a là ước của $F_{0}..F_{j-1}$ và $F_{j}$ , suy ra a cũng phải là ước của 2, mà a lớn hơn 1 nên a bằng 2. Điều này mâu thuẫn bởi mọi số Fermat là số lẻ.

Đồng thời như một kết quả tất yếu, ta tìm được cách chứng minh khác cho sự vô hạn của số nguyên tố. Với mỗi F_n, chọn một ước nguyên tố p_n thì dãy {p_n} tạo thành một dãy chứa vô hạn các số nguyên tố phân biệt.

Các tính chất khác

Không có số Fermat có thể biểu diễn thành hiệu của 2 lũy thừa bậc p với p là số nguyên tố lẻ.
Ngoại trừ F₀ và F₁, các số Fermat đều kết thúc bằng số 7.
Tổng của các nghịch đảo của các số Fermat là số vô tỉ.

Các giá trị đầu tiên

F₀	=	2¹	+	1	=	3
F₁	=	2²	+	1	=	5
F₂	=	2⁴	+	1	=	17
F₃	=	2⁸	+	1	=	257
F₄	=	2¹⁶	+	1	=	65 537
F₅	=	2³²	+	1	=	4 294 967 297
					=	641 × 6 700 417
F₆	=	2⁶⁴	+	1	=	18 446 744 073 709 551 617
					=	274 177 × 67 280 421 310 721
F₇	=	2¹²⁸	+	1	=	340 282 366 920 938 463 463 374 607 431 768 211 457
					=	59 649 589 127 497 217 × 5 704 689 200 685 129 054 721
F₈	=	2²⁵⁶	+	1	=	115 792 089 237 316 195 423 570 985 008 687 907 853 269 984 665 640 564 039 457 584 007 913 129 639 937
					=	1 238 926 361 552 897 × 93 461 639 715 357 977 769 163 558 199 606 896 584 051 237 541 638 188 580 280 321
F₉	=	2⁵¹²	+	1	=	13 407 807 929 942 597 099 574 024 998 205 846 127 479 365 820 592 393 377 723 561 443 721 764 030 073 546 976 801 874 298 166 903 427 690 031 858 186 486 050 853 753 882 811 946 569 946 433 649 006 084 097
					=	2 424 833 × 7 455 602 825 647 884 208 337 395 736 200 454 918 783 366 342 657 × 741 640 062 627 530 801 524 787 141 901 937 474 059 940 781 097 519 023 905 821 316 144 415 759 504 705 008 092 818 711 693 940 737

Lịch sử

Khi nghiên cứu các số có dạng 2^2ⁿ + 1, Fermat đã tính ra được với n = 0, 1, 2, 3, 4 thì số có dạng trên là số nguyên tố, từ đó ông đưa ra dự đoán các số có dạng như trên đều là số nguyên tố. Từ đó các số có dạng thức như trên được gọi là số Fermat.

Tuy nhiên đến năm 1732, Euler đã phủ định dự đoán trên bằng cách chứng minh F₅ là hợp số.

Phân tích ra thừa số nguyên tố

Bằng cách biểu thị:

641=5\times 2^{7}+1=2^{4}+5^{4}

Euler đã suy ra: $5\times 2^{7}\equiv -1{\pmod {641}}$ , dẫn đến $5^{4}\times 2^{28}\equiv (-1)^{4}\equiv 1{\pmod {641}}$ . Mặt khác $5^{4}\equiv -2^{4}{\pmod {641}}$ nên suy ra $-2^{32}\equiv 1{\pmod {641}}$ . Vậy F₅ chia hết cho 641.

Euler cũng đã chứng minh được mọi ước nguyên tố của F_n đều có dạng k2^{n + 2} + 1.

Đến nay người ta vẫn chưa tìm ra nổi thêm số Fermat nào nguyên tố nữa, trong khi đã có hơn 70 hợp số của số Fermat đã được kiểm chứng.

Một trong những cách phân tích có uy tín nhất hiện nay là phân tích F_n ra tổng hai bình phương (chúng có dạng 4k + 1, hoàn toàn làm được). Phân tích cơ bản nhất là:

F_{n}=\left(2^{2^{n-1}}\right)^{2}+1^{2}

.

Nếu như tồn tại một cách biểu diễn khác, giả dụ F_n = x² + y² (với x > y) thì tính kết quả của:

\gcd(x+2^{2^{n-1}}\times y,F_{n})

.

Ví dụ:

F₅ = 62 264² + 20 449², dẫn đến:

\gcd(62.264+2^{2^{4}}\times 20.449,F_{5})=641

.

F₆ = 4 046 803 256² + 1 438 793 759², dẫn đến:

\gcd(4.046.803.256+2^{2^{5}}\times 1.438.793.759,F_{6})=274.177

.

Nhờ đó người ta đã phân tích ra thừa số nguyên tố của các số từ F₅ đến F₁₁, thậm chí còn tìm ra ước nguyên tố của các số lớn hơn thế nữa.

Ví dụ:

F₁₉₄₅ = 2^2¹⁹⁴⁵ + 1 có khoảng 9,5929 × 10⁵⁸⁴ chữ số, nhờ phép phân tích trên tìm ra được ước số của nó là 5 × 2¹⁹⁴⁷ + 1 ≈ 6,3734 × 10⁵⁸⁶.
F_{2 478 782} = 2^{2^{2 478 782}} + 1 có khoảng 1,6343 × 10^{746 187} chữ số, nhờ phép phân tích trên tìm ra được ước số của nó là 3 × 2^{2 478 785} + 1 ≈ 1,3029 × 10^{746 189}, đây là hợp số Fermat lớn nhất đã biết từ trước đến nay.

Tính chất liên quan đến ước số

Ta có thể tính gần đúng số chữ số của chúng bằng hệ thức gần đúng:

D(n,b)=\lfloor \log _{b}\left(2^{2^{\overset {n}{}}}+1\right)+1\rfloor =\lfloor 2^{n}\,\log _{b}2+1\rfloor

Nếu 2^m + 1 là nguyên tố thì m là một lũy thừa của 2.
Ước nguyên tố của F_n luôn có dạng k2^{n + 2} + 1, với k > 2.

Ứng dụng trong dựng đa giác đều

Tham khảo

Liên kết ngoài

Fermat prime - Số nguyên tố Fermat tại Encyclopædia Britannica (tiếng Anh)
Chris Caldwell, The Prime Glossary: Fermat number at The Prime Pages.
Luigi Morelli, History of Fermat Numbers
John Cosgrave, Unification of Mersenne and Fermat Numbers Lưu trữ 2006-10-02 tại Wayback Machine
Wilfrid Keller, Prime Factors of Fermat Numbers Lưu trữ 2016-02-10 tại Wayback Machine
Weisstein, Eric W., "Fermat Number" từ MathWorld.
Weisstein, Eric W., "Fermat Prime" từ MathWorld.
Weisstein, Eric W., "Fermat Pseudoprime" từ MathWorld.
Weisstein, Eric W., "Generalized Fermat Number" từ MathWorld.
Yves Gallot, Generalized Fermat Prime Search
Mark S. Manasse, Complete factorization of the ninth Fermat number (original announcement)^{[liên kết hỏng]}
Peyton Hayslette, Largest Known Generalized Fermat Prime Announcement

x t s Pierre de Fermat
Công trình nghiên cứu	Định lý lớn Số Nguyên lý Định lý nhỏ Số đa giác đều Số giả nguyên tố Fermat Điểm Định lý Fermat (điểm đứng yên) Định lý tổng hai số chính phương Xoắn ốc Fermat Định lý tam giác vuông Fermat Kiểm tra Thương số
Liên quan	List of things named after Pierre de Fermat Chứng minh của Wiles về Định lý cuối cùng của Fermat Fermat's Last Theorem in fiction Giải Fermat Fermat's Last Tango (vở nhạc kịch năm 2000) Fermat's Last Theorem (sách) (sách khoa học phổ thông) 12007 Fermat

x t s Phân loại các số nguyên tố
Theo công thức	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Mersenne kép ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Giai thừa ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 u \cdot3 v + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 a \pm 2 b \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Carol $(2 n - 1) 2 - 2$ Kynea $(2 n + 1) 2 - 2$ Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
Theo dãy số nguyên	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Phân hoạch Bell Motzkin
Theo tính chất	(Cặp Wieferich) Wall–Sun–Sun Wolstenholme Wilson May rủi May mắn Ramanujan Pillai Chính quy Mạnh Stern Siêu trội (đối với đường cong elliptic) Siêu trội (trong thuyết Ánh trăng) Tốt Siêu phàm Higgs Fortune
Phụ thuộc vào hệ số	May mắn Nhị diện Palindromic Emirp Repunit $(10 n - 1)/9$ Hoán vị Vòng Rút ngắn được Strobogrammatic Tối thiểu Yếu Đầy đủ Đơn nhất Nguyên thủy Smarandache–Wellin
Theo mô hình	Sinh đôi ( $p, p + 2$ ) Chuỗi bộ đôi ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) Bộ tam ( $p, p + 2 or p + 4, p + 6$ ) Bộ tứ ( $p, p + 2, p + 6, p + 8$ ) Bộ k Họ hàng ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain ( $p, 2 p + 1$ ) chuỗi Cunningham ( $p, 2 p \pm 1, \dots$ ) An toàn ( $p, (p - 1)/2$ ) Trong cấp số cộng ( $p + a\cdotn, n = 0, 1, \dots$ ) Đối xứng ( $consecutive p - n, p, p + n$ )
Theo kích thước	Hàng nghìn (1,000+ chữ số) Hàng chục nghìn (10,000+ chữ số) Hàng triệu (1,000,000+ chữ số) Lớn nhất từng biết
Số phức	Số nguyên tố Eisenstein Số nguyên tố Gauss
Hợp số	Số giả nguyên tố Số gần nguyên tố Số nửa nguyên tố Giữa các nguyên tố
Chủ đề liên quan	Số có thể nguyên tố Số nguyên tố cấp công nghiệp Số nguyên tố bất chính Công thức của số nguyên tố Khoảng cách nguyên tố
50 số nguyên tố đầu	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229
Danh sách số nguyên tố