Числа Ферма

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

$F_n=2^{2^{\stackrel{n}{}}}+1$

де n — невід'ємне ціле число. Декілька перших чисел Ферма:

3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ... Шаблон:OEIS.

Якщо 2^k + 1 просте і k > 0, то k має бути ступенем 2, таким чином 2^k + 1 є числом Ферма. Такі прості називаються простими Ферма. Шаблон:As of рік відомо лише 5 простих чисел Ферма: F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, та F₄ = 65537 Шаблон:OEIS, інших таких чисел після Ферма знайдено не було і припускається, що інших не існує.

Властивості

• Числа Ферма задовольняють таким рекурентним співвідношенням:

1. $F_n=(F_{n-1}-1{)}^2+1$
2. $F_n=F_{n-1}+2^{2^{n-1}}{F}_0\cdots F_{n-2}$
3. $F_n=F_{n-1}^2-2(F_{n-2}-1{)}^2$
4. $F_n=F_0\cdots F_{n-1}+2$

Перша й третя рівність перевіряються за допомогою елементарних операцій.
Четверту рівність можна довести методом математичної індукції:

твердження очевидно правильне для n=1 : F₁ = F₀ +2;

якщо припустити істинність для декого цілого n, тоді:

$\prod _{k=0}^n{F}_k=(\prod _{k=0}^{n-1}{F}_k)F_n=(F_n-2)F_n=(2^{2^n}-1)(2^{2^n}+1)=2^{2^{n+1}}-1=F_{n+1}-2,$

що завершує доведення 4-ї рівності.

Друга рівність може бути зведена до четвертої:

$F_{n-1}+2^{2^{n-1}}{F}_0\cdots F_{n-2}=F_{n-1}+(F_{n-1}-1)F_0\cdots F_{n-2}=F_{n-1}+F_0\cdots F_{n-1}-F_0\cdots F_{n-2}=F_0\cdots F_{n-1}+2=F_n$

де двічі застосовано четверту рівність.

• Теорема Гольдбаха: будь-які два різні числа Ферма є взаємно-простими.

Це твердження випливає з останньої рекурсії. Справді, жодне з чисел Ферма не є парним, а якщо F_n і F_i, де n>i, взаємно-прості, тоді з попереднього маємо, що $F_n=F_i\cdot A+2,A\in Z.$ Отже, їх спільний дільник має ділити 2, що неможливо для непарних чисел.

• Жодне число Ферма не є сумою двох простих чисел, за винятком F₁ = 2 + 3.
• Правильний n-кутник можна побудувати за допомогою циркуля й лінійки тоді і лише тоді, коли $n=2^r{p}_1{p}_2\dots p_k$, де $p_i$ — різні прості числа Ферма (теорема Гаусса — Ванцеля).
• Серед чисел виду $2^n+1$ простими можуть бути тільки числа Ферма. Справді, якщо у $n$ є непарний дільник $m>1$, то згідно з теоремою Безу:

$2^n+1=(2^m+1)(1-2^m+2^{2m}-\cdots +2^{n-m}),$

і тому $2^n+1$ не є простим.

• Простота чисел Ферма ефективно визначається за допомогою тесту Пепіна: Число F_m просте тоді й тільки тоді, коли число $(3^{\frac{F_m-1}{2}}+1)$ ділиться на F_mШаблон:Sfn.
• Теорема Люка: всі прості дільники числа Ферма F_n, де n>1, мають вигляд k×2ⁿ⁺²+1.

Прості числа Ферма

П'єр Ферма висунув гіпотезу, що всі вони прості. Дійсно, легко показати, що перші п'ять чисел Ферма F₀, ..., F₄ є простими. Проте Леонард Ейлер визначив, що

$F_5=2^{2^5}+1=2^{32}+1=4294967297=641\times 6700417.$

Ейлер довів, що кожен дільник F_n має бути виду k∙2ⁿ⁺¹+1 (пізніше Едуар Люка посилив це твердження до k∙2ⁿ⁺²+1) для n ≥ 2.

Те, що 641 є дільником F₅ можна вивести з рівностей 641 = 2⁷ × 5 + 1 та 641 = 2⁴ + 5⁴. Із першої рівності випливає, що 2⁷ × 5 ≡ −1 (mod 641), і, підносячи до четвертого ступеня, що 2²⁸ × 5⁴ ≡ 1 (mod 641). З іншого боку, із другої рівності випливає, що 5⁴ ≡ −2⁴ (mod 641). Із цих конгруєнцій випливає, що 2³² ≡ −1 (mod 641).

Залишалися відкритими питання про існування інших простих чисел Ферма і про скінченність чи нескінченність множини таких чиселШаблон:Sfn.

Станом на 2014 рік відомоШаблон:Джерело?, що F_n є складеними для $5\le n\le 32$. Повна факторизація F_n відома для Шаблон:Nowrap, не відомо жодного дільника для Шаблон:Nowrap та Шаблон:Nowrap.
У жовтні 2020 року було знайдено найбільше відоме складене число Ферма — це F_18233954, його дільник Шаблон:NowrapШаблон:Джерело?.

Факторизація чисел Ферма

Через великий розмір чисел Ферма, вкрай важко виконати їх повну факторизацію або навіть перевірити на простоту. Едуар Люка в 1878 році довів, що кожен дільник числа Ферма F_n має бути виду k∙2ⁿ⁺²+1, де k — додатне ціле. Це числа Прота. Відшукання простих Прота дозволяє легко провести тест на простоту чисел Ферма.
На сучасних комп'ютерах необхідні й достатні умови для визначення простоти чисел Ферма дає також тест Пепіна.
Шаблон:Джерело?. У проєкті розподілених обчислень Fermatsearch знайдено декілька дільників чисел Ферма. Для пошуку дільників великих чисел Ферма застосовується програма proth.exe авторства Іва Ґалу (Шаблон:Lang-fr).

Факторизація перших дванадцяти чисел Ферма:

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 році )
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^{2^{\stackrel{n}{}}}+b^{2^{\stackrel{n}{}}}$, де a, b будь-які взаємно-прості числа, такі що a > b > 0, називаються узагальненими числами Ферма. Непарне просте p є узагальненим числом Ферма тоді і тільки тоді, коли $p\equiv 1(\mathrm{mod}4)$. (Ми розглядаємо тільки випадок, коли n > 0, отже 3 = $2^{2^0}+1$ не є контрприкладом.)

За аналогією зі звичайними числами Ферма прийнято записувати узагальнені числа Ферма виду $a^{2^{\stackrel{n}{}}}+1$ як F_n(Шаблон:Mvar). У цьому позначенні, наприклад, число 100'000'001 буде записано як F₃(10). Далі ми обмежимося простими числами цього виду, $a^{2^{\stackrel{n}{}}}+1$, такі прості числа називаються "прості Ферма за основою Шаблон:Mvar". Звичайно, ці прості числа існують лише тоді, коли Шаблон:Mvar парне.

Узагальнені прості Ферма

Через легкість доведення їх простоти, останніми роками узагальнені прості числа Ферма стали темою для досліджень у галузі теорії чисел. Багато з найбільших відомих сьогодні простих чисел є узагальненими простими числами Ферма.

Узагальнені числа Ферма можуть бути простими лише для парних Шаблон:Mvar, оскільки якщо Шаблон:Mvar непарне, то кожне узагальнене число Ферма буде ділитися на 2. Найменше просте число $F_n(a)$ з $n>4$ — це $F_5(30)$ або 30³² + 1.

Література

• 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

• Шаблон:Cite journal Часть 2 Часть 3
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite web

Див. також

• Список об'єктів, названих на честь П'єра Ферма