Числа Ферма

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

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

Властивості

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

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

$F_{n} = F_{n-1} + 2^{2^{n-1}}F_{0} \cdots F_{n-2}$

$F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2$

$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_n, де n>1, мають вигляд k2ⁿ⁺²+1.

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

Французький математик П'єр Ферма на честь якого названі дані числа висунув гіпотезу, що всі вони прості. Проте Ейлер визначив, що F₅ = 4294967297 = 641 × 6700417. Зараз відомо 5 простих чисел Ферма: $3; 5; 17; 257; 65537$. Відомо, що, $F_n$ не є простими для $5 \le n \le 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

Посилання

• Леонид Дурман «Гонки по вертикали. Числа Ферма от Эйлера до наших дней: начало, продолжение, окончание». Компьютерра, №№ 393-395, 2001.