For faster navigation, this Iframe is preloading the Wikiwand page for Числа Ферма.

Числа Ферма

Матеріал з Вікіпедії — вільної енциклопедії.

У математиці числами Ферма, що названі на честь французького математика П'єра Ферма, який першим дослідив їх, є числа виду:

де 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 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 (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.

Примітки

[ред. | ред. код]
  1. а б Леонид Дурман, 2001.
  2. 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

Див. також

[ред. | ред. код]
{{bottomLinkPreText}} {{bottomLinkText}}
Числа Ферма
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?