Числа Ферма

У математиці числом Ферма називається число виду:

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

де n — невід'ємне ціле число.
Перші дев'ять чисел Ферма:

F0	=	21	+	1	=	3
F1	=	22	+	1	=	5
F2	=	24	+	1	=	17
F3	=	28	+	1	=	257
F4	=	216	+	1	=	65537
F5	=	232	+	1	=	4294967297
					=	641 × 6700417
F6	=	264	+	1	=	18446744073709551617
					=	274177 × 67280421310721
F7	=	2128	+	1	=	340282366920938463463374607431768211457
					=	59649589127497217 × 5704689200685129054721
F8	=	2256	+	1	=	115792089237316195423570985008687907853269984665640564039457584007913129639937
					=	1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321.

Властивості

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

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₅ = 4294967297 = 641 × 6700417. Зараз відомо лише 5 простих чисел Ферма: $3;5;17;257;65537$, інших таких чисел після Ферма знайдено не було. Відомо, що $F_{n}$ не є простими для $5\leq n\leq 32$. Залишаються відкритими питання про існування інших простих чисел Ферма і про скінченність чи нескінченність множини таких чисел.

Література

• 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. 

Див. також

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