www.wikidata.uk-ua.nina.az

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

Числа Ферма

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

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

Якщо 2k + 1 просте і k > 0, то k має бути ступенем 2, таким чином 2k + 1 є числом Ферма. Такі прості називаються простими Ферма. Станом на 2023 рік відомо лише 5 простих чисел Ферма: F0 = 3, F1 = 5, F2 = 17, F3 = 257, та F4 = 65537 послідовність A019434 з Онлайн енциклопедії послідовностей цілих чисел, OEIS, інших таких чисел після Ферма знайдено не було і припускається, що інших не існує.

Властивості Редагувати

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

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

де двічі застосовано четверту рівність.

Це твердження випливає з останньої рекурсії. Справді, жодне з чисел Ферма не є парним, а якщо Fn і Fi, де n>i, взаємно-прості, тоді з попереднього маємо, що Отже, їх спільний дільник має ділити 2, що неможливо для непарних чисел.

  • Жодне число Ферма не є сумою двох простих чисел, за винятком F1 = 2 + 3.
  • Правильний n-кутник можна побудувати за допомогою циркуля й лінійки тоді і лише тоді, коли , де  — різні прості числа Ферма (теорема Гаусса — Ванцеля).
  • Серед чисел виду простими можуть бути тільки числа Ферма. Справді, якщо у є непарний дільник , то згідно з теоремою Безу:

Прості числа Ферма Редагувати

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

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

Те, що 641 є дільником F5 можна вивести з рівностей 641 = 27 × 5 + 1 та 641 = 24 + 54. Із першої рівності випливає, що 27 × 5 ≡ −1 (mod 641), і, підносячи до четвертого ступеня, що 228 × 54 ≡ 1 (mod 641). З іншого боку, із другої рівності випливає, що 54 ≡ −24 (mod 641). Із цих конгруєнцій випливає, що 232 ≡ −1 (mod 641).

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

Станом на 2014 рік відомо[джерело?], що Fn є складеними для . Повна факторизація Fn відома для 0 ≤ n ≤ 11, не відомо жодного дільника для n = 20 та n = 24.
У жовтні 2020 року було знайдено найбільше відоме складене число Ферма — це F18233954, його дільник 7 × 218233956 + 1[джерело?].

Факторизація чисел Ферма Редагувати

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

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

Узагальнені числа Ферма Редагувати

Числа виду , де a, b будь-які взаємно-прості числа, такі що a > b > 0, називаються узагальненими числами Ферма. Непарне просте p є узагальненим числом Ферма тоді і тільки тоді, коли . (Ми розглядаємо тільки випадок, коли n > 0, отже 3 = не є контрприкладом.)

За аналогією зі звичайними числами Ферма прийнято записувати узагальнені числа Ферма виду як Fn(a). У цьому позначенні, наприклад, число 100'000'001 буде записано як F3(10). Далі ми обмежимося простими числами цього виду, , такі прості числа називаються "прості Ферма за основою a". Звичайно, ці прості числа існують лише тоді, коли a парне.

Узагальнені прості Ферма Редагувати

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

Узагальнені числа Ферма можуть бути простими лише для парних a, оскільки якщо a непарне, то кожне узагальнене число Ферма буде ділитися на 2. Найменше просте число з — це або 3032 + 1.

Примітки Редагувати

  1. ↑ Леонид Дурман, 2001.
  2. Sandifer, Ed. How Euler Did it. 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, ISBN 0-387-95332-9
  • Леонид Дурман (24 апреля). . Гонки по вертикали. Числа Ферма от Эйлера до наших дней. Компьютерра (№16). 
  • Michael A. Morrison & John Brillhart (1975). . [Continued fraction method]. Math. Comp 29: 183–205. 
  • Richard P. Brent & John M. Pollard (1981). . [Pollard rho algorithm]. Math. Comp 36: 627–630. 
  • A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse & J. M. Pollard (1993). . [Number field sieve]. Math. Comp 61: 319–349. 
  • Richard P. Brent (1999). . [Elliptic curve method]. Math. Comp 68: 429–451. 
  • Jeff Young & Duncan A. Buell (1988). . Math. Comp 50: 261–263. 
  • Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003). . Math. Comp 72: 1555–1572. 
  • Wilfrid Keller (25 червня 2023). Prime factors k·2n + 1 of Fermat numbers Fm and complete factoring status. Proth Search. Процитовано 8 липня 2023. 

Див. також Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U matematici chislami Ferma sho nazvani na chest francuzkogo matematika P yera Ferma yakij pershim doslidiv yih ye chisla vidu F n 2 2 n 1 displaystyle F n 2 2 overset n 1 de n nevid yemne cile chislo Dekilka pershih chisel Ferma 3 5 17 257 65537 4294967297 18446744073709551617 poslidovnist A000215 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Yaksho 2k 1 proste i k gt 0 to k maye buti stupenem 2 takim chinom 2k 1 ye chislom Ferma Taki prosti nazivayutsya prostimi Ferma Stanom na 2023 rik vidomo lishe 5 prostih chisel Ferma F0 3 F1 5 F2 17 F3 257 ta F4 65537 poslidovnist A019434 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS inshih takih chisel pislya Ferma znajdeno ne bulo i pripuskayetsya sho inshih ne isnuye Zmist 1 Vlastivosti 2 Prosti chisla Ferma 3 Faktorizaciya chisel Ferma 4 Uzagalneni chisla Ferma 4 1 Uzagalneni prosti Ferma 5 Primitki 6 Literatura 7 Div takozhVlastivosti RedaguvatiChisla Ferma zadovolnyayut takim rekurentnim spivvidnoshennyam F n F n 1 1 2 1 displaystyle F n F n 1 1 2 1 nbsp F n F n 1 2 2 n 1 F 0 F n 2 displaystyle F n F n 1 2 2 n 1 F 0 cdots F n 2 nbsp F n F n 1 2 2 F n 2 1 2 displaystyle F n F n 1 2 2 F n 2 1 2 nbsp F n F 0 F n 1 2 displaystyle F n F 0 cdots F n 1 2 nbsp Persha j tretya rivnist pereviryayutsya za dopomogoyu elementarnih operacij Chetvertu rivnist mozhna dovesti metodom matematichnoyi indukciyi tverdzhennya ochevidno pravilne dlya n 1 F1 F0 2 yaksho pripustiti istinnist dlya dekogo cilogo n todi k 0 n F k 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 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 nbsp sho zavershuye dovedennya 4 yi rivnosti Druga rivnist mozhe buti zvedena do chetvertoyi F n 1 2 2 n 1 F 0 F n 2 F n 1 F n 1 1 F 0 F n 2 F n 1 F 0 F n 1 F 0 F n 2 F 0 F n 1 2 F n 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 nbsp de dvichi zastosovano chetvertu rivnist Teorema Goldbaha bud yaki dva rizni chisla Ferma ye vzayemno prostimi Ce tverdzhennya viplivaye z ostannoyi rekursiyi Spravdi zhodne z chisel Ferma ne ye parnim a yaksho Fn i Fi de n gt i vzayemno prosti todi z poperednogo mayemo sho F n F i A 2 A Z displaystyle F n F i cdot A 2 A in Z nbsp Otzhe yih spilnij dilnik maye diliti 2 sho nemozhlivo dlya neparnih chisel Zhodne chislo Ferma ne ye sumoyu dvoh prostih chisel za vinyatkom F1 2 3 Pravilnij n kutnik mozhna pobuduvati za dopomogoyu cirkulya j linijki todi i lishe todi koli n 2 r p 1 p 2 p k displaystyle n 2 r p 1 p 2 dots p k nbsp de p i displaystyle p i nbsp rizni prosti chisla Ferma teorema Gaussa Vancelya Sered chisel vidu 2 n 1 displaystyle 2 n 1 nbsp prostimi mozhut buti tilki chisla Ferma Spravdi yaksho u n displaystyle n nbsp ye neparnij dilnik m gt 1 displaystyle m gt 1 nbsp to zgidno z teoremoyu Bezu 2 n 1 2 m 1 1 2 m 2 2 m 2 n m displaystyle 2 n 1 2 m 1 1 2 m 2 2m cdots 2 n m nbsp i tomu 2 n 1 displaystyle 2 n 1 nbsp ne ye prostim Prostota chisel Ferma efektivno viznachayetsya za dopomogoyu testu Pepina Chislo Fm proste todi j tilki todi koli chislo 3 F m 1 2 1 displaystyle 3 frac F m 1 2 1 nbsp dilitsya na Fm 1 Teorema Lyuka vsi prosti dilniki chisla Ferma Fn de n gt 1 mayut viglyad k 2n 2 1 Prosti chisla Ferma RedaguvatiP yer Ferma visunuv gipotezu sho vsi voni prosti Dijsno legko pokazati sho pershi p yat chisel Ferma F0 F4 ye prostimi Prote Leonard Ejler viznachiv sho F 5 2 2 5 1 2 32 1 4294967297 641 6700417 displaystyle F 5 2 2 5 1 2 32 1 4294967297 641 times 6700417 nbsp Ejler doviv sho kozhen dilnik Fn maye buti vidu k 2n 1 1 piznishe Eduar Lyuka posiliv ce tverdzhennya do k 2n 2 1 dlya n 2 Te sho 641 ye dilnikom F5 mozhna vivesti z rivnostej 641 27 5 1 ta 641 24 54 Iz pershoyi rivnosti viplivaye sho 27 5 1 mod 641 i pidnosyachi do chetvertogo stupenya sho 228 54 1 mod 641 Z inshogo boku iz drugoyi rivnosti viplivaye sho 54 24 mod 641 Iz cih kongruyencij viplivaye sho 232 1 mod 641 Zalishalisya vidkritimi pitannya pro isnuvannya inshih prostih chisel Ferma i pro skinchennist chi neskinchennist mnozhini takih chisel 1 Stanom na 2014 rik vidomo dzherelo sho Fn ye skladenimi dlya 5 n 32 displaystyle 5 leq n leq 32 nbsp Povna faktorizaciya Fn vidoma dlya 0 n 11 ne vidomo zhodnogo dilnika dlya n 20 ta n 24 U zhovtni 2020 roku bulo znajdeno najbilshe vidome skladene chislo Ferma ce F18233954 jogo dilnik 7 218233956 1 dzherelo Faktorizaciya chisel Ferma RedaguvatiCherez velikij rozmir chisel Ferma vkraj vazhko vikonati yih povnu faktorizaciyu abo navit pereviriti na prostotu Eduar Lyuka v 1878 roci doviv sho kozhen dilnik chisla Ferma Fn maye buti vidu k 2n 2 1 de k dodatne cile Ce chisla Prota Vidshukannya prostih Prota dozvolyaye legko provesti test na prostotu chisel Ferma Na suchasnih komp yuterah neobhidni j dostatni umovi dlya viznachennya prostoti chisel Ferma daye takozh test Pepina Metod eliptichnih krivih ye najshvidshim dlya vidshukannya vidnosno malih dilnikiv chisel dzherelo U proyekti rozpodilenih obchislen Fermatsearch znajdeno dekilka dilnikiv chisel Ferma Dlya poshuku dilnikiv velikih chisel Ferma zastosovuyetsya programa proth exe avtorstva Iva Galu fr Yves Gallot Faktorizaciya pershih dvanadcyati chisel Ferma F0 21 1 3 prosteF1 22 1 5 prosteF2 24 1 17 prosteF3 28 1 257 prosteF4 216 1 65 537 najbilshe vidome proste FermaF5 232 1 4 294 967 297 641 6 700 417 faktorizovano povnistyu v 1732 roci 2 F6 264 1 18 446 744 073 709 551 617 20 cifr 274 177 67 280 421 310 721 faktorizovano povnistyu 1855 roci F7 2128 1 340 282 366 920 938 463 463 374 607 431 768 211 457 39 cifr faktorizovano povnistyu v 1970 roci 59 649 589 127 497 217 5 704 689 200 685 129 054 721F8 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 cifr faktorizovane povnistyu v 1980 roci 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 321F9 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 cifr 2 424 833 7 455 602 825 647 884 208 337 395 736 200 454 918 783 366 342 657 49 cifr 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 cifr faktorizovane povnistyu v 1990 roci F10 21024 1 179 769 313 486 231 590 772 930 304 835 356 329 624 224 137 217 309 cifr 45 592 577 6 487 031 809 4 659 775 785 220 018 543 264 560 743 076 778 192 897 40 cifr 130 439 874 405 488 189 727 484 806 217 820 753 127 014 424 577 252 cifri faktorizovane povnistyu v 1995 roci F11 22048 1 32 317 006 071 311 007 300 714 8 193 555 853 611 059 596 230 657 617 cifr 319 489 974 849 167 988 556 341 760 475 137 21 cifra 3 560 841 906 445 833 920 513 22 cifri 173 462 447 179 147 555 430 258 491 382 441 723 306 598 834 177 564 cifri faktorizovane povnistyu v 1988 roci Uzagalneni chisla Ferma RedaguvatiChisla vidu a 2 n b 2 n displaystyle a 2 overset n b 2 overset n nbsp de a b bud yaki vzayemno prosti chisla taki sho a gt b gt 0 nazivayutsya uzagalnenimi chislami Ferma Neparne proste p ye uzagalnenim chislom Ferma todi i tilki todi koli p 1 mod 4 displaystyle p equiv 1 pmod 4 nbsp Mi rozglyadayemo tilki vipadok koli n gt 0 otzhe 3 2 2 0 1 displaystyle 2 2 0 1 nbsp ne ye kontrprikladom Za analogiyeyu zi zvichajnimi chislami Ferma prijnyato zapisuvati uzagalneni chisla Ferma vidu a 2 n 1 displaystyle a 2 overset n 1 nbsp yak Fn a U comu poznachenni napriklad chislo 100 000 001 bude zapisano yak F3 10 Dali mi obmezhimosya prostimi chislami cogo vidu a 2 n 1 displaystyle a 2 overset n 1 nbsp taki prosti chisla nazivayutsya prosti Ferma za osnovoyu a Zvichajno ci prosti chisla isnuyut lishe todi koli a parne Uzagalneni prosti Ferma Redaguvati Cherez legkist dovedennya yih prostoti ostannimi rokami uzagalneni prosti chisla Ferma stali temoyu dlya doslidzhen u galuzi teoriyi chisel Bagato z najbilshih vidomih sogodni prostih chisel ye uzagalnenimi prostimi chislami Ferma Uzagalneni chisla Ferma mozhut buti prostimi lishe dlya parnih a oskilki yaksho a neparne to kozhne uzagalnene chislo Ferma bude dilitisya na 2 Najmenshe proste chislo F n a displaystyle F n a nbsp z n gt 4 displaystyle n gt 4 nbsp ce F 5 30 displaystyle F 5 30 nbsp abo 3032 1 Primitki Redaguvati a b Leonid Durman 2001 Sandifer Ed How Euler Did it MAA Online Mathematical Association of America Procitovano 13 chervnya 2020 Literatura Redaguvati17 Lectures on Fermat Numbers From Number Theory to Geometry Michal Krizek Florian Luca Lawrence Somer Springer CMS Books 9 ISBN 0 387 95332 9Leonid Durman 24 aprelya Chast 1 Gonki po vertikali Chisla Ferma ot Ejlera do nashih dnej Kompyuterra 16 Chast 2 Chast 3 Michael A Morrison amp John Brillhart 1975 A method of factoring and the factorization of F7 Continued fraction method Math Comp 29 183 205 Richard P Brent amp 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 amp 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 amp Duncan A Buell 1988 The twentieth Fermat number is composite Math Comp 50 261 263 Richard E Crandall Ernst W Mayer amp Jason S Papadopoulos 2003 The twenty fourth Fermat number is composite Math Comp 72 1555 1572 Wilfrid Keller 25 chervnya 2023 Prime factors k 2n 1 of Fermat numbers Fm and complete factoring status Proth Search Procitovano 8 lipnya 2023 Div takozh RedaguvatiSpisok ob yektiv nazvanih na chest P yera Ferma Otrimano z https uk wikipedia org w index php title Chisla Ferma amp oldid 40646843