Перегляд вихідного коду сторінки Числа Ферма

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

: <math>F_{n} = 2^{2^{ \overset{n} {}}} + 1</math>

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

: [[3 (число)|3]], [[5 (число)|5]], [[17 (число)|17]], [[257 (число)|257]], [[65537 (число)|65537]], 4294967297, 18446744073709551617, ... {{OEIS|id=A000215}}.

Якщо 2<sup>''k''</sup> + 1 просте і ''k'' > 0, то ''k'' має бути ступенем 2, таким чином 2<sup>''k''</sup> + 1 є числом Ферма. Такі прості називаються '''простими Ферма'''. {{As of|{{CURRENTYEAR}}}} рік відомо лише 5 [[Просте число|простих чисел]] Ферма: ''F''<sub>0</sub> = 3, ''F''<sub>1</sub> = 5, ''F''<sub>2</sub> = 17, ''F''<sub>3</sub> = 257, та ''F''<sub>4</sub> = 65537 {{OEIS|id=A019434}}, інших таких чисел після Ферма знайдено не було і припускається, що інших не існує.

== Властивості ==
* Числа Ферма задовольняють таким [[рекурентне співвідношення|рекурентним співвідношенням]]:

# <math>F_{n} = (F_{n-1}-1)^{2}+1\,</math>
# <math>F_{n} = F_{n-1} + 2^{2^{n-1}}F_{0} \cdots F_{n-2}</math>
# <math>F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2</math>
# <math>F_{n} = F_{0} \cdots F_{n-1} + 2</math>
Перша й третя рівність перевіряються за допомогою елементарних операцій.
<br/>Четверту рівність можна довести [[Математична індукція|методом математичної індукції]]: 
: твердження очевидно правильне для ''n=1'' : ''F''<sub>1</sub> = ''F''<sub>0</sub> +2;
: якщо припустити істинність для декого цілого ''n'', тоді:
: <math>\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,</math>
: що завершує доведення 4-ї рівності.

Друга рівність може бути зведена до четвертої:
: <math>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}</math>
де двічі застосовано четверту рівність.
 
* '''Теорема Гольдбаха''': будь-які два різні числа Ферма є [[взаємно прості числа|взаємно-простими]].
Це твердження випливає з останньої рекурсії. Справді, жодне з чисел Ферма не є [[парні числа|парним]], а якщо ''F''<sub>n</sub> і ''F''<sub>i</sub>, де ''n>i'', взаємно-прості, тоді з попереднього маємо, що <math>F_n = F_i \cdot A +2, A \in Z.</math> Отже, їх спільний дільник має ділити 2, що неможливо для непарних чисел.

* Жодне число Ферма не є сумою двох простих чисел, за винятком ''F''<sub>1</sub> = 2 + 3.
* [[Правильний многокутник|Правильний ''n''-кутник]] можна побудувати за допомогою циркуля й лінійки тоді і лише тоді, коли <math>n=2^r p_1 p_2\dots p_k</math>, де <math>p_i</math>&nbsp;— різні прості числа Ферма ([[теорема Гаусса — Ванцеля]]).
* Серед чисел виду <math>2^n+1</math> простими можуть бути тільки числа Ферма. Справді, якщо у <math>n</math> є непарний [[дільник]] <math>m>1</math>, то згідно з [[теорема Безу|теоремою Безу]]:
: <math>2^n+1=(2^m+1)(1-2^m+2^{2m}-\cdots+2^{n-m}),</math>
: і тому <math>2^n+1</math> не є простим.
* Простота чисел Ферма ефективно визначається за допомогою [[тест Пепіна|тесту Пепіна]]: Число F<sub>m</sub> просте тоді й тільки тоді, коли число <math>(3^{\frac{F_m - 1}{2} } + 1)</math> ділиться на F<sub>m</sub>{{sfn|Леонид Дурман|2001|}}.
* [[Теорема Люка]]: всі [[Простий множник|прості дільники]] числа Ферма ''F''<sub>n</sub>, де ''n>1'', мають вигляд ''k×2<sup>n+2</sup>+1''.

== Прості числа Ферма ==
[[П'єр Ферма]] висунув гіпотезу, що всі вони прості. Дійсно, легко показати, що перші п'ять чисел Ферма ''F''<sub>0</sub>, ..., ''F''<sub>4</sub> є простими. Проте [[Леонард Ейлер]] визначив, що

:<math> F_{5} = 2^{2^5} + 1 = 2^{32} + 1 = 4294967297 = 641 \times 6700417. </math>

Ейлер довів, що кожен дільник ''F''<sub>''n''</sub> має бути виду ''k''∙2<sup>''n''+1</sup>+1 (пізніше [[Едуар Люка]] посилив це твердження до ''k''∙2<sup>''n''+2</sup>+1) для ''n'' ≥ 2.

Те, що 641 є дільником ''F''<sub>5</sub> можна вивести з рівностей 641&nbsp;=&nbsp;2<sup>7</sup>&nbsp;×&nbsp;5&nbsp;+&nbsp;1 та 641&nbsp;=&nbsp;2<sup>4</sup>&nbsp;+&nbsp;5<sup>4</sup>. Із першої рівності випливає, що 2<sup>7</sup>&nbsp;×&nbsp;5&nbsp;≡&nbsp;−1&nbsp;(mod&nbsp;641), і, підносячи до четвертого ступеня, що 2<sup>28</sup>&nbsp;×&nbsp;5<sup>4</sup>&nbsp;≡&nbsp;1&nbsp;(mod&nbsp;641). З іншого боку, із другої рівності випливає, що 5<sup>4</sup>&nbsp;≡&nbsp;−2<sup>4</sup>&nbsp;(mod&nbsp;641). Із цих [[Модульна арифметика|конгруєнцій]] випливає, що 2<sup>32</sup>&nbsp;≡&nbsp;−1&nbsp;(mod&nbsp;641).

Залишалися відкритими питання про існування інших простих чисел Ферма і про скінченність чи нескінченність [[множина|множини]] таких чисел{{sfn|Леонид Дурман|2001|}}.

Станом на 2014 рік відомо{{Джерело?}}, що ''F''<sub>n</sub> є складеними для <math>5 \le n \le 32</math>. Повна факторизація ''F''<sub>n</sub> відома для {{nowrap|0 ≤ ''n'' ≤ 11}}, не відомо жодного дільника для {{nowrap|1=''n'' = 20}} та {{nowrap|1=''n'' = 24}}. 
<br/>У жовтні 2020 року було знайдено найбільше відоме [[складене число]] Ферма — це ''F''<sub>18233954</sub>, його дільник {{nowrap|7 × 2<sup>18233956</sup> + 1}}{{Джерело?}}.

== Факторизація чисел Ферма ==
Через великий розмір чисел Ферма, вкрай важко виконати їх повну [[Факторизація цілих чисел|факторизацію]] або навіть перевірити на простоту. [[Едуар Люка]] в 1878 році довів, що кожен дільник числа Ферма ''F''<sub>n</sub> має бути виду ''k''∙2<sup>''n''+2</sup>+1, де ''k'' — додатне ціле. Це [[числа Прота]]. Відшукання простих Прота дозволяє легко провести тест на простоту чисел Ферма. <br/>На сучасних комп'ютерах необхідні й достатні умови для визначення простоти чисел Ферма дає також [[тест Пепіна]]. <br/>{{Джерело?|[[Факторизація методом еліптичних кривих|Метод еліптичних кривих]] є найшвидшим для відшукання відносно малих дільників чисел}}. У проєкті [[Розподілені обчислення|розподілених обчислень]] ''Fermatsearch'' знайдено декілька дільників чисел Ферма. Для пошуку дільників великих чисел Ферма застосовується програма <code>proth.exe</code> авторства Іва Ґалу ({{lang-fr|Yves Gallot}}). 

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

:{|
|- valign="top"
|''F''<sub>0</sub> ||=|| 2<sup>1</sup>||+||1 ||=||[[3 (число)|3]] — просте||
|- valign="top"
|''F''<sub>1</sub> ||=|| 2<sup>2</sup>||+||1 ||=||[[5 (число)|5]] — просте||
|- valign="top"
|''F''<sub>2</sub> ||=|| 2<sup>4</sup>||+||1 ||=||[[17 (число)|17]] — просте||
|- valign="top"
|''F''<sub>3</sub> ||=|| 2<sup>8</sup>||+||1 ||=||[[257 (число)|257]] — просте||
|- valign="top"
|''F''<sub>4</sub> ||=|| 2<sup>16</sup>||+||1 ||=||[[65537 (число)|65 537]] — найбільше відоме просте Ферма||
|- valign="top"
|''F''<sub>5</sub> ||=|| 2<sup>32</sup>||+||1 ||=||4 294 967 297||
|- style="background:white; color:#700000"
| || || || || ||=||641 × 6 700 417 (факторизовано повністю в 1732 році <ref>{{cite web |last1=Sandifer |first1=Ed |title=How Euler Did it |url=http://eulerarchive.maa.org/hedi/HEDI-2007-03.pdf |website=MAA Online |publisher=Mathematical Association of America |access-date=2020-06-13}}</ref>)
|- valign="top"
|''F''<sub>6</sub> ||=|| 2<sup>64</sup>||+||1 ||=||18 446 744 073 709 551 617 (20 цифр) ||
|- style="background:white; color:#700000"
| || || || || ||=||274 177 × 67 280 421 310 721 (факторизовано повністю 1855 році)
|- valign="top"
|''F''<sub>7</sub> ||=|| 2<sup>128</sup>||+||1 ||=||340 282 366 920 938 463 463 374 607 431 768 211 457 (39 цифр, факторизовано повністю в 1970 році)||
|- style="background:white; color:#700000"
| || || || || ||=||59 649 589 127 497 217  × 5 704 689 200 685 129 054 721
|- valign="top"
|''F''<sub>8</sub> ||=|| 2<sup>256</sup>||+||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 році)||
|- style="background:white; color:#700000; vertical-align:top"
| || || || || ||=||1 238 926 361 552 897 × <br>93 461 639 715 357 977 769 163 558 199 606 896 584 051 237 541 638 188 580 280 321 
|- valign="top"
|''F''<sub>9</sub> ||=|| 2<sup>512</sup>||+||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'<br>030'073'546'976'801'874'298'166'903'427'690'031'858'186'486'050'853'753'882'811'946'569'946'433'<br>649'006'084'097 (155 цифр)||
|- style="background:white; color:#700000; vertical-align:top"
| || || || || ||=|| 2'424'833 × 7'455'602'825'647'884'208'337'395'736'200'454'918'783'366'342'657 (49 цифр) × <br>741'640'062'627'530'801'524'787'141'901'937'474'059'940'781'097'519'023'905'821'316'144'415'759'<br>504'705'008'092'818'711'693'940'737 (99 цифр) (факторизоване повністю в 1990 році)
|- valign="top"
|''F''<sub>10</sub> ||=|| 2<sup>1024</sup>||+||1
||=||179'769'313'486'231'590'772'930...304'835'356'329'624'224'137'217 (309 цифр)||
|- style="background:white; color:#700000; vertical-align:top"
| || || || || ||=||45'592'577 × 6'487'031'809 × 4'659'775'785'220'018'543'264'560'743'076'778'192'897 (40 цифр) × <br>130'439'874'405'488'189'727'484...806'217'820'753'127'014'424'577 (252 цифри) (факторизоване повністю в 1995 році)
|- valign="top"
|''F''<sub>11</sub> ||=|| 2<sup>2048</sup>||+||1
||=||32'317'006'071'311'007'300'714'8...193'555'853'611'059'596'230'657 (617 цифр)||
|- style="background:white; color:#700000; vertical-align:top"
| || || || || ||=|| 319'489 × 974'849 × 167'988'556'341'760'475'137 (21 цифра) × 3'560'841'906'445'833'920'513 (22 цифри) × <br>173'462'447'179'147'555'430'258...491'382'441'723'306'598'834'177 (564 цифри) (факторизоване повністю в 1988 році)
|-
|}

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

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

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

Узагальнені числа Ферма можуть бути простими лише для парних {{mvar|a}}, оскільки якщо {{mvar|a}} непарне, то кожне узагальнене число Ферма буде ділитися на 2. Найменше просте число <math>F_n(a)</math> з <math>n>4</math> — це <math>F_5(30)</math> або 30<sup>32</sup> + 1.

== Примітки ==
{{reflist|refs=}}

== Література ==
* ''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|author=Леонид Дурман |title= Гонки по вертикали. Числа Ферма от Эйлера до наших дней | chapterurl=https://web.archive.org/web/20090822095903/http://offline.computerra.ru/2001/393/8925/ |chapter=Часть 1 |journal=Компьютерра |issue=№16 |date= 24 апреля |year=2001 |ref=harv}} [https://web.archive.org/web/20090822100126/http://offline.computerra.ru/2001/394/9233/ Часть 2]  [https://web.archive.org/web/20090822095907/http://offline.computerra.ru/2001/395/9428/ Часть 3]
* {{cite journal |author= Michael A. Morrison & John Brillhart |title=A method of factoring and the factorization of F<sub>7</sub>
|journal=Math. Comp |volume=29 |year=1975 |pages= 183-205 |url= https://web.archive.org/web/20160924014618/http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0371800-5/S0025-5718-1975-0371800-5.pdf |others=[Continued fraction method]}}
* {{cite journal |author= Richard P. Brent & John M. Pollard |title= Factorization of the eighth Fermat number |journal=Math. Comp |volume=36 |year= 1981 |pages= 627-630 |url= https://web.archive.org/web/20160924014618/http://www.ams.org/journals/mcom/1981-36-154/S0025-5718-1981-0606520-5/S0025-5718-1981-0606520-5.pdf |others=[Pollard rho algorithm]}}
* {{cite journal |author= A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse & J. M. Pollard |title=The factorization of the ninth Fermat number |journal= Math. Comp |volume=61 |year=1993 |pages= 319-349 |url=https://web.archive.org/web/20160924014618/http://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1182953-4/S0025-5718-1993-1182953-4.pdf |others= [Number field sieve]}}
* {{cite journal |author= Richard P. Brent |title = Factorization of the tenth Fermat number |journal=Math. Comp |volume=68 |year=1999 |pages= 429-451 |url= https://web.archive.org/web/20160924014618/http://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00992-8/S0025-5718-99-00992-8.pdf |others=[Elliptic curve method]}}
* {{cite journal |author= Jeff Young & Duncan A. Buell |title=The twentieth Fermat number is composite |journal= Math. Comp |volume=50 |year=1988 |pages= 261-263  |url= https://web.archive.org/web/20160924014618/http://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988-0917833-8/S0025-5718-1988-0917833-8.pdf}}
* {{cite journal |author= Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos |title= The twenty-fourth Fermat number is composite |journal= Math. Comp |volume=72 |year=2003 |pages= 1555-1572 |url= https://web.archive.org/web/20160924014618/http://www.ams.org/journals/mcom/2003-72-243/S0025-5718-02-01479-5/S0025-5718-02-01479-5.pdf}}
* {{cite web|title=Prime factors k·2<sup>n</sup> + 1  of Fermat numbers F<sub>m</sub> and complete factoring status |url=http://www.prothsearch.com/fermat.html#Summary|work=Proth Search|date=25 червня 2023|author= Wilfrid Keller |accessdate=2023-07-08}}

== Див. також ==
* [[Список об'єктів, названих на честь П'єра Ферма]]

{{Класи натуральних чисел}}

[[Категорія:Теорія чисел]]
[[Категорія:цілочисельні послідовності]]
[[Категорія:Числа з власними іменами]]
[[Категорія:Нерозв'язані проблеми математики]]