Числа Ферма

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

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

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

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

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

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

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

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

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

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

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 (14 цифр) (факторизоване повністю в 1855 році)
F7	=	2128	+	1	=	340'282'366'920'938'463'463'374'607'431'768'211'457 (39 цифр)
					=	59'649'589'127'497'217 (17 цифр) × 5'704'689'200'685'129'054'721 (22 цифри) (факторизоване повністю в 1970 році)
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 цифр)
					=	1'238'926'361'552'897 (16 цифр) × 93'461'639'715'357'977'769'163'558'199'606'896'584'051'237'541'638'188'580'280'321 (62 цифри) (факторизоване повністю в 1980 році)
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^{\overset {n}{}}}\!\!+b^{2^{\overset {n}{}}}$, де a, b будь-які взаємно-прості числа, такі що a > b > 0, називаються узагальненими числами Ферма. Непарне просте p є узагальненим числом Ферма тоді і тільки тоді, коли $p\equiv 1{\pmod {4}}$. (Ми розглядаємо тільки випадок, коли n > 0, отже 3 = $2^{2^{0}}\!+1$ не є контрприкладом.)

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

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

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

Узагальнені числа Ферма можуть бути простими лише для парних a, оскільки якщо a непарне, то кожне узагальнене число Ферма буде ділитися на 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

• Леонид Дурман (24 апреля). Часть 1. Гонки по вертикали. Числа Ферма от Эйлера до наших дней. Компьютерра (№16).  Часть 2 Часть 3
• Michael A. Morrison & John Brillhart (1975). A method of factoring and the factorization of F₇. [Continued fraction method]. Math. Comp 29: 183–205. 
• Richard P. Brent & John M. Pollard (1981). Factorization of the eighth Fermat number. [Pollard rho algorithm]. Math. Comp 36: 627–630. 
• A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse & J. M. Pollard (1993). The factorization of the ninth Fermat number. [Number field sieve]. Math. Comp 61: 319–349. 
• Richard P. Brent (1999). Factorization of the tenth Fermat number. [Elliptic curve method]. Math. Comp 68: 429–451. 
• Jeff Young & Duncan A. Buell (1988). The twentieth Fermat number is composite. Math. Comp 50: 261–263. 
• Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003). The twenty-fourth Fermat number is composite. Math. Comp 72: 1555–1572. 

Див. також

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