Số Fermat

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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^{ \overset{n} {}}} + 1.

với n là số nguyên không âm.

Các giá trị đầu tiên[sửa | sửa mã nguồn]

F0 = 21 + 1 = 3
F1 = 22 + 1 = 5
F2 = 24 + 1 = 17
F3 = 28 + 1 = 257
F4 = 216 + 1 = 65 537
F5 = 232 + 1 = 4 294 967 297
= 641 × 6 700 417
F6 = 264 + 1 = 18 446 744 073 709 551 617
= 274 177 × 67 280 421 310 721
F7 = 2128 + 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
F8 = 2256 + 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
F9 = 2512 + 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ử[sửa | sửa mã nguồn]

Khi nghiên cứu các số có dạng 22n + 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 F5 là hợp số.

Phân tích ra thừa số nguyên tố[sửa | sửa mã nguồn]

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 F5 chia hết cho 641.

Euler cũng đã chứng minh được mọi ước nguyên tố của Fn đều có dạng k2n + 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 Fn 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ụ Fn = x2 + y2 (với x > y) thì tính kết quả của:

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

Ví dụ:

  • F5 = 62 2642 + 20 4492, dẫn đến:
\gcd (62.264 + 2^{2^4} \times 20.449,F_5) = 641.
  • F6 = 4 046 803 2562 + 1 438 793 7592, 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ừ F5 đến F11, 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ụ:

  • F1945 = 221945 + 1 có khoảng 9,5929 × 10584 chữ số, nhờ phép phân tích trên tìm ra được ước số của nó là 5 × 21947 + 1 ≈ 6,3734 × 10586.
  • F2 478 782 = 222 478 782 + 1 có khoảng 1,6343 × 10746 187 chữ số, nhờ phép phân tích trên tìm ra được ước số của nó là 3 × 22 478 785 + 1 ≈ 1,3029 × 10746 189, đây là hợp số Fermat lớn nhất đã biết từ trước đến nay.

Tính chất[sửa | sửa mã nguồn]

  • Với "n" ≥ 2, các hệ thức dưới đây có thể chứng minh bằng cách quy nạp:
F_{n} = (F_{n-1}-1)^{2}+1\,
F_{n} = F_{n-1} + 2^{2^{n-1}}F_{0} \cdots F_{n-2}
F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2
F_{n} = F_{0} \cdots F_{n-1} + 2

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 2m + 1 là nguyên tố thì m là một lũy thừa của 2.
  • Ước nguyên tố của Fn luôn có dạng k2n + 2 + 1, với k > 2.

Ứng dụng trong dựng đa giác đều[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]