У математиці числами Ферма, що названі на честь французького математика П'єра Ферма, який першим дослідив їх, є числа виду:
де n — невід'ємне ціле число. Декілька перших чисел Ферма:
- 3, 5, 17, (257), , 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.
- Теорема Люка: всі прості дільники числа Ферма 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).
Залишалися відкритими питання про існування інших простих чисел Ферма і про скінченність чи нескінченність множини таких чисел.
Станом на 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 = — найбільше відоме просте Ферма F5 = 232 + 1 = 4 294 967 297 = 641 × 6 700 417 (факторизовано повністю в 1732 році ) 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,
- Леонид Дурман (24 апреля). Гонки по вертикали. Числа Ферма от Эйлера до наших дней. Компьютерра (№16).
{{}}
: Проігноровано|chapter=
() - Michael A. Morrison & John Brillhart (1975). [Continued fraction method]. (PDF). Math. Comp. 29: 183—205.
- Richard P. Brent & John M. Pollard (1981). [Pollard rho algorithm]. (PDF). Math. Comp. 36: 627—630.
- A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse & J. M. Pollard (1993). [Number field sieve]. (PDF). Math. Comp. 61: 319—349.
- Richard P. Brent (1999). [Elliptic curve method]. (PDF). Math. Comp. 68: 429—451.
- Jeff Young & Duncan A. Buell (1988). (PDF). Math. Comp. 50: 261—263.
- Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003). (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.
Див. також
- (Список об'єктів, названих на честь П'єра Ферма)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет