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

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

${\displaystyle F_{n}=2^{2^{\overset {n}{}}}+1}$

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

3, 5, 17, 257, , 4294967297, 18446744073709551617, ... послідовність A000215 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.

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

Властивості

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

1. ${\displaystyle F_{n}=(F_{n-1}-1)^{2}+1\,}$
2. ${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}}$
3. ${\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}}$
4. ${\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2}$

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

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

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

${\displaystyle \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-ї рівності.

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

${\displaystyle 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, взаємно-прості, тоді з попереднього маємо, що ${\displaystyle F_{n}=F_{i}\cdot A+2,A\in Z.}$ Отже, їх спільний дільник має ділити 2, що неможливо для непарних чисел.

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

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

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

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

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

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

${\displaystyle 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).

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

Станом на 2014 рік відомо^[], що F_n є складеними для ${\displaystyle 5\leq n\leq 32}$. Повна факторизація F_n відома для 0 ≤ n ≤ 11, не відомо жодного дільника для n = 20 та n = 24.
У жовтні 2020 року було знайдено найбільше відоме складене число Ферма — це F_18233954, його дільник 7 × 2^18233956 + 1^[].

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

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

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

F0	=	2^1	+	1	=	3 — просте
F1	=	2^2	+	1	=	5 — просте
F2	=	2^4	+	1	=	17 — просте
F3	=	2^8	+	1	=	257 — просте
F4	=	2^16	+	1	=	— найбільше відоме просте Ферма
F5	=	2^32	+	1	=	4 294 967 297
					=	641 × 6 700 417 (факторизовано повністю в 1732 році )
F6	=	2^64	+	1	=	18 446 744 073 709 551 617 (20 цифр)
					=	274 177 × 67 280 421 310 721 (факторизовано повністю 1855 році)
F7	=	2^128	+	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	=	2^256	+	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	=	2^512	+	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	=	2^1024	+	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	=	2^2048	+	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 році)

Узагальнені числа Ферма

Числа виду ${\displaystyle a^{2^{\overset {n}{}}}\!\!+b^{2^{\overset {n}{}}}}$, де a, b будь-які взаємно-прості числа, такі що a > b > 0, називаються узагальненими числами Ферма. Непарне просте p є узагальненим числом Ферма тоді і тільки тоді, коли ${\displaystyle p\equiv 1{\pmod {4}}}$. (Ми розглядаємо тільки випадок, коли n > 0, отже 3 = ${\displaystyle 2^{2^{0}}\!+1}$ не є контрприкладом.)

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

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

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

Узагальнені числа Ферма можуть бути простими лише для парних a, оскільки якщо a непарне, то кожне узагальнене число Ферма буде ділитися на 2. Найменше просте число ${\displaystyle F_{n}(a)}$ з ${\displaystyle n>4}$ — це ${\displaystyle F_{5}(30)}$ або 30³² + 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,

• Леонид Дурман (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·2ⁿ + 1 of Fermat numbers F_m and complete factoring status. Proth Search. Процитовано 8 липня 2023.

Див. також

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