Числа Ферма
У математиці числами Ферма, що названі на честь французького математика П'єра Ферма, який першим дослідив їх, є числа виду:
де n — невід'ємне ціле число. Декілька перших чисел Ферма:
- 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ... послідовність A000215 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.
Якщо 2k + 1 просте і k > 0, то k має бути ступенем 2, таким чином 2k + 1 є числом Ферма. Такі прості називаються простими Ферма. Станом на 2024 рік відомо лише 5 простих чисел Ферма: F0 = 3, F1 = 5, F2 = 17, F3 = 257, та F4 = 65537 послідовність A019434 з Онлайн енциклопедії послідовностей цілих чисел, OEIS, інших таких чисел після Ферма знайдено не було і припускається, що інших не існує.
- Числа Ферма задовольняють таким рекурентним співвідношенням:
Перша й третя рівність перевіряються за допомогою елементарних операцій.
Четверту рівність можна довести методом математичної індукції:
- твердження очевидно правильне для n=1 : F1 = F0 +2;
- якщо припустити істинність для декого цілого n, тоді:
- що завершує доведення 4-ї рівності.
Друга рівність може бути зведена до четвертої:
де двічі застосовано четверту рівність.
- Теорема Гольдбаха: будь-які два різні числа Ферма є взаємно-простими.
Це твердження випливає з останньої рекурсії. Справді, жодне з чисел Ферма не є парним, а якщо Fn і Fi, де n>i, взаємно-прості, тоді з попереднього маємо, що Отже, їх спільний дільник має ділити 2, що неможливо для непарних чисел.
- Жодне число Ферма не є сумою двох простих чисел, за винятком F1 = 2 + 3.
- Правильний n-кутник можна побудувати за допомогою циркуля й лінійки тоді і лише тоді, коли , де — різні прості числа Ферма (теорема Гаусса — Ванцеля).
- Серед чисел виду простими можуть бути тільки числа Ферма. Справді, якщо у є непарний дільник , то згідно з теоремою Безу:
- і тому не є простим.
- Простота чисел Ферма ефективно визначається за допомогою тесту Пепіна: Число Fm просте тоді й тільки тоді, коли число ділиться на Fm[1].
- Теорема Люка: всі прості дільники числа Ферма Fn, де n>1, мають вигляд k×2n+2+1.
П'єр Ферма висунув гіпотезу, що всі вони прості. Дійсно, легко показати, що перші п'ять чисел Ферма F0, ..., F4 є простими. Проте Леонард ��йлер визначив, що
Ейлер довів, що кожен дільник Fn має бути виду k∙2n+1+1 (пізніше Едуар Люка посилив це твердження до k∙2n+2+1) для n ≥ 2.
Те, що 641 є дільником F5 можна вивести з рівностей 641 = 27 × 5 + 1 та 641 = 24 + 54. Із першої рівності випливає, що 27 × 5 ≡ −1 (mod 641), і, підносячи до четвертого ступеня, що 228 × 54 ≡ 1 (mod 641). З іншого боку, із другої рівності випливає, що 54 ≡ −24 (mod 641). Із цих конгруєнцій випливає, що 232 ≡ −1 (mod 641).
Залишалися відкритими питання про існування інших простих чисел Ферма і про скінченність чи нескінченність множини таких чисел[1].
Станом на 2014 рік відомо[джерело?], що Fn є складеними для . Повна факторизація Fn відома для 0 ≤ n ≤ 11, не відомо жодного дільника для n = 20 та n = 24.
У жовтні 2020 року було знайдено найбільше відоме складене число Ферма — це F18233954, його дільник 7 × 218233956 + 1[джерело?].
Через великий розмір чисел Ферма, вкрай важко виконати їх повну факторизацію або навіть перевірити на простоту. Едуар Люка в 1878 році довів, що кожен дільник числа Ферма Fn має бути виду k∙2n+2+1, де k — додатне ціле. Це числа Прота. Відшукання простих Прота дозволяє легко провести тест на простоту чисел Ферма.
На сучасних комп'ютерах необхідні й достатні умови для визначення простоти чисел Ферма дає також тест Пепіна.
Метод еліптичних кривих є найшвидшим для відшукання відносно малих дільників чисел[джерело?]. У проєкті розподілених обчислень Fermatsearch знайдено декілька дільників чисел Ферма. Для пошуку дільників великих чисел Ферма застосовується програма proth.exe
авторства Іва Ґалу (фр. Yves Gallot).
Факторизація перших дванадцяти чисел Ферма:
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 (факторизовано повністю в 1732 році [2]) F6 = 264 + 1 = 18 446 744 073 709 551 617 (20 цифр) = 274 177 × 67 280 421 310 721 (факторизовано повністю 1855 році) F7 = 2128 + 1 = 340 282 366 920 938 463 463 374 607 431 768 211 457 (39 цифр, факторизовано повністю в 1970 році) = 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 (78 цифр, факторизоване повністю в 1980 році) = 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 321F9 = 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 (155 цифр)= 2'424'833 × 7'455'602'825'647'884'208'337'395'736'200'454'918'783'366'342'657 (49 цифр) ×
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 (99 цифр) (факторизоване повністю в 1990 році)F10 = 21024 + 1 = 179'769'313'486'231'590'772'930...304'835'356'329'624'224'137'217 (309 цифр) = 45'592'577 × 6'487'031'809 × 4'659'775'785'220'018'543'264'560'743'076'778'192'897 (40 цифр) ×
130'439'874'405'488'189'727'484...806'217'820'753'127'014'424'577 (252 цифри) (факторизоване повністю в 1995 році)F11 = 22048 + 1 = 32'317'006'071'311'007'300'714'8...193'555'853'611'059'596'230'657 (617 цифр) = 319'489 × 974'849 × 167'988'556'341'760'475'137 (21 цифра) × 3'560'841'906'445'833'920'513 (22 цифри) ×
173'462'447'179'147'555'430'258...491'382'441'723'306'598'834'177 (564 цифри) (факторизоване повністю в 1988 році)
Числа виду , де a, b будь-які взаємно-прості числа, такі що a > b > 0, називаються узагальненими числами Ферма. Непарне просте p є узагальненим числом Ферма тоді і тільки тоді, коли . (Ми розглядаємо тільки випадок, коли n > 0, отже 3 = не є контрприкладом.)
За аналогією зі звичайними числами Ферма прийнято записувати узагальнені числа Ферма виду як Fn(a). У цьому позначенні, наприклад, число 100'000'001 буде записано як F3(10). Далі ми обмежимося простими числами цього виду, , такі прості числа називаються "прості Ферма за основою a". Звичайно, ці прості числа існують лише тоді, коли a парне.
Через легкість доведення їх простоти, останніми роками узагальнені прості числа Ферма стали темою для досліджень у галузі теорії чисел. Багато з найбільших відомих сьогодні простих чисел є узагальненими простими числами Ферма.
Узагальнені числа Ферма можуть бути простими лише для парних a, оскільки якщо a непарне, то кожне узагальнене число Ферма буде ділитися на 2. Найменше просте число з — це або 3032 + 1.
- ↑ а б Леонид Дурман, 2001.
- ↑ Sandifer, Ed. How Euler Did it (PDF). MAA Online. Mathematical Association of America. Процитовано 13 червня 2020.
- 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Michal Křížek, Florian Luca, Lawrence Somer, Springer, CMS Books 9, ISBN 0-387-95332-9
- Леонид Дурман (24 апреля). Гонки по вертикали. Числа Ферма от Эйлера до наших дней. Компьютерра (№16).
{{cite journal}}
: Проігноровано|chapter=
(довідка) Часть 2 Часть 3 - Michael A. Morrison & John Brillhart (1975). [Continued fraction method]. A method of factoring and the factorization of F7 (PDF). Math. Comp. 29: 183—205.
- Richard P. Brent & John M. Pollard (1981). [Pollard rho algorithm]. Factorization of the eighth Fermat number (PDF). Math. Comp. 36: 627—630.
- A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse & J. M. Pollard (1993). [Number field sieve]. The factorization of the ninth Fermat number (PDF). Math. Comp. 61: 319—349.
- Richard P. Brent (1999). [Elliptic curve method]. Factorization of the tenth Fermat number (PDF). Math. Comp. 68: 429—451.
- Jeff Young & Duncan A. Buell (1988). The twentieth Fermat number is composite (PDF). Math. Comp. 50: 261—263.
- Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003). The twenty-fourth Fermat number is composite (PDF). Math. Comp. 72: 1555—1572.
- Wilfrid Keller (25 червня 2023). Prime factors k·2n + 1 of Fermat numbers Fm and complete factoring status. Proth Search. Процитовано 8 липня 2023.