Movatterモバイル変換

[0]ホーム
URL:

Przejdź do zawartości
Wikipediawolna encyklopedia
Szukaj

Liczby Mersenne’a

Z Wikipedii, wolnej encyklopedii

Liczby Mersenne’a – liczby postaciMn=2n−1,{\displaystyle M_{n}=2^{n}-1,} gdzien{\displaystyle n} jestliczbą naturalną[1]. Liczby Mersenne’a zostały tak nazwane na cześć francuskiego matematykaMarina Mersenne’a, który opublikował tablicęliczb pierwszych tego typu (jak się później okazało, błędną).

Liczba Mersenne’aMn{\displaystyle M_{n}} jest równa sumieciągu geometrycznego

20+21+22+23+…+2n−1.{\displaystyle 2^{0}+2^{1}+2^{2}+2^{3}+\ldots +2^{n-1}.}

Pierwszość liczb Mersenne’a

[edytuj |edytuj kod]

Warunkiem koniecznym, żeby liczbaMn{\displaystyle M_{n}} była pierwsza jest, byn{\displaystyle n} było liczbą pierwszą.

Rzeczywiście, niechn=ab{\displaystyle n=ab} będzieliczbą złożoną, gdziea,b>1{\displaystyle a,b>1} są liczbami naturalnymi. Wówczas

Mn=2n−1=2ab−1=(2a)b−1b={\displaystyle M_{n}=2^{n}-1=2^{ab}-1=(2^{a})^{b}-1^{b}=}
=(2a−1)(2a(b−1)+2a(b−2)+2a(b−3)+…+2a(b−b)){\displaystyle =(2^{a}-1)(2^{a(b-1)}+2^{a(b-2)}+2^{a(b-3)}+\ldots +2^{a(b-b)})}

również jest złożona.

Pierwszość wskaźnikan{\displaystyle n} nie jest jednak wystarczająca dla pierwszości liczbyMn,{\displaystyle M_{n},} np.:

M11=211−1=23⋅89.{\displaystyle M_{11}=2^{11}-1=23\cdot 89.}

Liczby złożone Mersenne’a

[edytuj |edytuj kod]

Nie wiadomo, czy istnieje nieskończenie wiele liczb złożonych Mersenne’a o wykładnikach będących liczbami pierwszymi. Ich przykładami są:

211−1=2047=23⋅89{\displaystyle 2^{11}-1=2047=23\cdot 89}
223−1=8388607=47⋅178481{\displaystyle 2^{23}-1=8388607=47\cdot 178481}
229−1=536870911=233⋅1103⋅2089{\displaystyle 2^{29}-1=536870911=233\cdot 1103\cdot 2089}
237−1=137438953471=223⋅616318177{\displaystyle 2^{37}-1=137438953471=223\cdot 616318177}
241−1=2199023255551=13367⋅164511353{\displaystyle 2^{41}-1=2199023255551=13367\cdot 164511353}
243−1=8796093022207=431⋅9719⋅2099863{\displaystyle 2^{43}-1=8796093022207=431\cdot 9719\cdot 2099863}
247−1=140737488355327=2351⋅4513⋅13264529{\displaystyle 2^{47}-1=140737488355327=2351\cdot 4513\cdot 13264529}
253−1=9007199254740991=6361⋅69431⋅20394401{\displaystyle 2^{53}-1=9007199254740991=6361\cdot 69431\cdot 20394401}
259−1=576460752303423487=179951⋅3203431780337{\displaystyle 2^{59}-1=576460752303423487=179951\cdot 3203431780337}[2]
283−1=9671406556917033397649407=167⋅57912614113275649087721{\displaystyle 2^{83}-1=9671406556917033397649407=167\cdot 57912614113275649087721}

Hipoteza byłaby prawdziwa, gdyby okazało się, że istnieje nieskończenie wieleliczb pierwszych Germain mających postać4k+3.{\displaystyle 4k+3.}

Liczby pierwsze Mersenne’a

[edytuj |edytuj kod]

Nie wiadomo, czy istnieje nieskończenie wiele liczb pierwszych Mersenne’a. Obecnie poznano ich 52[3]:

Lp.nMnMnLiczba cyfr wMnData odkryciaOdkrywca
1.222−1{\displaystyle 2^{2}-1}31
2.323−1{\displaystyle 2^{3}-1}71
3.525−1{\displaystyle 2^{5}-1}312
4.727−1{\displaystyle 2^{7}-1}1273
5.13213−1{\displaystyle 2^{13}-1}819141456nieznany
6.17217−1{\displaystyle 2^{17}-1}13107161588Pietro Cataldi(inne języki)
7.19219−1{\displaystyle 2^{19}-1}52428761588Pietro Cataldi
8.31231−1{\displaystyle 2^{31}-1}2147483647101772Leonhard Euler
9.61261−1{\displaystyle 2^{61}-1}2305843009213693951191883Iwan Perwuszin(inne języki)
10.89289−1{\displaystyle 2^{89}-1}618970019642690137449562111271911Ralph Ernest Powers(inne języki)
11.1072107−1{\displaystyle 2^{107}-1}162259276829213363391578010288127331914Ralph Ernest Powers
12.1272127−1{\displaystyle 2^{127}-1}1701411834604692317316873037158841057273910 czerwca 1876Édouard Lucas
13.5212521−1{\displaystyle 2^{521}-1}68647976601306097149...1257402829111505715115730 stycznia 1952Raphael Mitchel Robinson(inne języki)
14.6072607−1{\displaystyle 2^{607}-1}53113799281676709868...7083539321903172812718330 stycznia 1952Raphael Mitchel Robinson
15.127921279−1{\displaystyle 2^{1279}-1}10407932194664399081...2071055570316872908738625 czerwca 1952Raphael Mitchel Robinson
16.2 20322203−1{\displaystyle 2^{2203}-1}14759799152141802350...504194976866977710076647 października 1952Raphael Mitchel Robinson
17.2 28122281−1{\displaystyle 2^{2281}-1}44608755718375842957...641331724181328363516879 października 1952Raphael Mitchel Robinson
18.3 21723217−1{\displaystyle 2^{3217}-1}25911708601320262777...461606773629093150719698 września 1957Hans Riesel(inne języki)
19.4 25324253−1{\displaystyle 2^{4253}-1}19079700752443907380...760346878153504849911 2813 listopada 1961Alexander Hurwitz
20.4 42324423−1{\displaystyle 2^{4423}-1}28554254222827961390...102310579026085806071 3323 listopada 1961Alexander Hurwitz
21.9 68929689−1{\displaystyle 2^{9689}-1}47822027880546120295...189926968262257541112 91711 maja 1963Donald Bruce Gillies(inne języki)
22.9 94129941−1{\displaystyle 2^{9941}-1}34608828249085121524...194262248837894635512 99316 maja 1963Donald Bruce Gillies
23.11 213211213−1{\displaystyle 2^{11213}-1}28141120136973731333...673914760876963921913 3762 czerwca 1963Donald Bruce Gillies
24.19 937219937−1{\displaystyle 2^{19937}-1}43154247973881626480...367415390309680414716 0024 marca 1971Bryant Tuckerman(inne języki)
25.21 701221701−1{\displaystyle 2^{21701}-1}44867916611904333479...574108283535118827516 53330 października 1978Landon Curt Noll(inne języki) i Laura Nickel
26.23 209223209−1{\displaystyle 2^{23209}-1}40287411577898877818...367433555237792645116 9879 lutego 1979Landon Curt Noll
27.44 497244497−1{\displaystyle 2^{44497}-1}85450982430363380319...4486768696101122867113 3958 kwietnia 1979Harry Lewis Nelson(inne języki) iDavid Slowinski(inne języki)
28.86 243286243−1{\displaystyle 2^{86243}-1}53692799550275632152...9985702170943343820725 96225 września 1982David Slowinski
29.110 5032110503−1{\displaystyle 2^{110503}-1}52192831334175505976...6995162108346551500733 26528 stycznia 1988Walt Colquitt i Luke Welsh
30.132 0492132049−1{\displaystyle 2^{132049}-1}51274027626932072381...5213857845573006131139 75119 września 1983David Slowinski
31.216 0912216091−1{\displaystyle 2^{216091}-1}74609310306466134368...9133620410381552844765 0506 września 1985David Slowinski
32.756 8392756839−1{\displaystyle 2^{756839}-1}17413590682008709732...02603793328544677887227 83219 lutego 1992David Slowinski(inne języki) i Paul Gage
33.859 4332859433−1{\displaystyle 2^{859433}-1}12949812560420764966...02414267243500142591258 71610 stycznia 1994David Slowinski i Paul Gage
34.1 257 78721257787−1{\displaystyle 2^{1257787}-1}41224577362142867472...31257188976089366527378 6323 września 1996David Slowinski i Paul Gage
35.1 398 26921398269−1{\displaystyle 2^{1398269}-1}81471756441257307514...85532025868451315711420 92113 listopada 1996GIMPS / Joel Armengaud
36.2 976 22122976221−1{\displaystyle 2^{2976221}-1}62334007624857864988...76506256743729201151895 93224 sierpnia 1997GIMPS / Gordon Spence
37.3 021 37723021377−1{\displaystyle 2^{3021377}-1}12741168303009336743...25422631973024694271909 52627 stycznia 1998GIMPS / Roland Clarkson
38.6 972 59326972593−1{\displaystyle 2^{6972593}-1}43707574412708137883...353665261429241937912 098 9601 czerwca 1999GIMPS / Nayan Hajratwala
39.13 466 917213466917−1{\displaystyle 2^{13466917}-1}92494773800670132224...300738554702562590714 053 94614 listopada 2001GIMPS / Michael Cameron
40.20 996 011220996011−1{\displaystyle 2^{20996011}-1}12597689545033010502...947140657628556820476 320 43017 listopada 2003GIMPS / Michael Shafer
41.24 036 583224036583−1{\displaystyle 2^{24036583}-1}29941042940415717208...674369218827339694077 235 73315 maja 2004GIMPS / Josh Findley
42.25 964 951225964951−1{\displaystyle 2^{25964951}-1}12216463006127794810...989332572805770772477 816 23018 lutego 2005GIMPS / Martin Nowak
43.30 402 457230402457−1{\displaystyle 2^{30402457}-1}31541647561884608093...111342974116529438719 152 05215 grudnia 2005GIMPS / Curtis Cooper i Steven Boone
44.32 582 657232582657−1{\displaystyle 2^{32582657}-1}12457502601536945540...117528801540539678719 808 3584 września 2006GIMPS / Curtis Cooper i Steven Boone
45.37 156 667237156667−1{\displaystyle 2^{37156667}-1}20225440689097733553...2134026502230822092711 185 2726 września 2008GIMPS / Hans-Michael Elvenich
46.42 643 801242643801−1{\displaystyle 2^{42643801}-1}16987351645274162247...8410195476556231475112 837 0644 czerwca 2009GIMPS / Odd Magnar Strindmo
47.43 112 609243112609−1{\displaystyle 2^{43112609}-1}31647026933025592314...8002218116669715251112 978 18923 sierpnia 2008GIMPS / Edson Smith
48.57 885 161257885161−1{\displaystyle 2^{57885161}-1}58188726623224644217...4614198807172428595117 425 17025 stycznia 2013GIMPS / Curtis Cooper[4]
49.74 207 281274207281−1{\displaystyle 2^{74207281}-1}30037641808460618205...8701007339108643635122 338 6187 stycznia 2016GIMPS / Curtis Cooper[5]
50.*77 232 917277232917−1{\displaystyle 2^{77232917}-1}46733318335923109998...8273061806976217907123 249 42526 grudnia 2017GIMPS / Jonathan Pace[6]
51.*82 589 933282589933−1{\displaystyle 2^{82589933}-1}14889444574204132554...3795121032521790259124 862 0487 grudnia 2018GIMPS / Patrick Laroche[7]
52.*136 279 8412136279841−1{\displaystyle 2^{136279841}-1}88169432750383326555...5507670621948687155141 024 32012 października 2024GIMPS / Luke Durant[8]

* Czerwiec 2025: Numeracja tymczasowa. Nie wiadomo czy między liczbami M74207281 i M136279841 nie ma innych jeszcze nieodkrytych liczb pierwszych Mersenne’a.

Test Lucasa-Lehmera

[edytuj |edytuj kod]

Pierwszość liczb Mersenne’a sprawdza się za pomocątestu Lucasa-Lehmera:

Przyjmijmy

S1 = 4

i następnie

Sk = Sk−12 −2

Liczba Mp jest liczbą pierwszą wtedy i tylko wtedy, gdy:

Sp−1 ≡ 0 mod Mp.

Przykład zastosowania testu Lucasa:Rozważmy M7 = 127

  • S1 = 4
  • S2 = 42 − 2 = 14
  • S3 = 142 − 2 = 194 ≡ 67 (mod 127)
  • S4 = 672 − 2 = 4487 ≡ 42 (mod 127)
  • S5 = 422 − 2 = 1762 ≡ 111 (mod 127)
  • S6 = 1112 − 2 = 12319 ≡ 0 (mod 127)

liczba M7 = 27−1 = 127 jest liczbą pierwszą.

Największa liczba pierwsza Mersenne’a

[edytuj |edytuj kod]

Największą obecnie znaną liczbą pierwszą Mersenne’a jest2136279841−1.{\displaystyle 2^{136279841}-1.} Odkrył ją 12 października 2024 roku Luke Durant[8] w ramach projektuGIMPS. Do jej zapisania wukładzie dziesiętnym potrzeba41 024 320cyfr. Współcześnie poszukiwaniem liczb pierwszych Mersenne’a i rozkładaniem liczb złożonych naczynniki pierwsze zajmują się projektyobliczeń rozproszonych. Czołowym z nich jest właśnie GIMPS, do którego należy odkrycie ostatnich największych znanych liczb pierwszych[9].

Liczby Mersenne’a a liczby doskonałe

[edytuj |edytuj kod]
Wikipedia:Weryfikowalność
Ta sekcja od 2018-05 wymagazweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formieprzypisów bibliograficznych.
Część lub nawet wszystkie informacje w sekcji mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach:Encyklopedia PWN •Google Books • Google Scholar •BazHum •BazTech •RCIN • Internet Archive (texts /inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się wdyskusji tej sekcji.
Po wyeliminowaniu niedoskonałości należy usunąć szablon{{Dopracować}} z tej sekcji.

Liczby Mersenne’a są związane z odnajdywaniem kolejnychliczb doskonałych, ponieważ występują we wzorze, który je generuje:2n−1⋅(2n−1),{\displaystyle 2^{n-1}\cdot (2^{n}-1),} gdzie wyrażenie2n−1{\displaystyle 2^{n}-1} to liczba pierwsza Mersenne’aMn{\displaystyle M_{n}}[10].

Związek liczb złożonych Mersenne’a z liczbami pierwszymi Germain

[edytuj |edytuj kod]

Twierdzenie: Liczba Mersenne’a2p−1{\displaystyle 2^{p}-1} jest złożona i podzielna przezq:=2p+1{\displaystyle q:=2p+1} dla dowolnejliczby pierwszejGermainp≡−1(mod4).{\displaystyle p\equiv -1\!\!\!\!{\pmod {4}}.}

Dowód: Na mocytwierdzenia o wzajemności kwadratowej, kongruencjax2≡2(modq){\displaystyle x^{2}\equiv 2\!\!\!\!{\pmod {q}}} ma rozwiązanie dla liczby pierwszej nieparzystejq{\displaystyle q} wtedy i tylko wtedy, gdyq≡1 lub −1(mod8).{\displaystyle q\equiv 1{\mbox{ lub }}-1\!\!\!\!{\pmod {8}}.}

Niechp≡−1(mod4){\displaystyle p\equiv -1\!\!\!\!{\pmod {4}}} będzieliczbą pierwszą Germain, czylip=4a−1{\displaystyle p=4a-1} jest pierwsze, orazq:=2p+1{\displaystyle q:=2p+1} jest liczbą pierwszą. Wtedyq=8a−1,{\displaystyle q=8a-1,} więc istnieje liczba całkowitar{\displaystyle r} taka, żer2≡2(modq).{\displaystyle r^{2}\equiv 2\!\!\!\!{\pmod {q}}.} Zatem na mocyMałego Twierdzenia Fermata:2p−1=rq−1−1≡0(modq).{\displaystyle 2^{p}-1=r^{q-1}-1\equiv 0\!\!\!\!{\pmod {q}}.}

Przykłady:p=11, 23, 83.{\displaystyle p=11,\ 23,\ 83.}

Przypisy

[edytuj |edytuj kod]
  1. ↑Liczby Mersenne’a, [w:]Encyklopedia PWN [online],Wydawnictwo Naukowe PWN [dostęp 2021-09-15] .
  2. ↑table of factors of small Mersenne numbers. planetmath.org. [dostęp 2022-06-03]. (ang.).
  3. ↑Mersenne Prime [online], mathworld.wolfram.com [dostęp 2024-10-21] (ang.).
  4. ↑GIMPS Discovers 48th Mersenne Prime. [dostęp 2019-01-09]. (ang.).
  5. ↑GIMPS Project Discovers Largest Known Prime Number:274207281−1{\displaystyle 2^{74207281}-1}. [dostęp 2019-01-09]. (ang.).
  6. ↑GIMPS Project Discovers Largest Known Prime Number:277232917−1{\displaystyle 2^{77232917}-1}. [dostęp 2019-01-09]. (ang.).
  7. ↑GIMPS Project Discovers Largest Known Prime Number:282589933−1{\displaystyle 2^{82589933}-1}. mersenne.org, 2021-12-21. [dostęp 2019-01-09]. (ang.).
  8. ↑abGIMPS Discovers Largest Known Prime Number:2136279841−1{\displaystyle 2^{136279841}-1}. mersenne.org, 2024-10-21. [dostęp 2024-10-21]. (ang.).
  9. ↑List of Known Mersenne Prime Numbers. [dostęp 2019-01-09]. (ang.).
  10. ↑Włodzimierz Holsztyński: Liczby doskonałe. [dostęp 2019-01-09]. [zarchiwizowane ztego adresu (2019-01-10)]. (pol.).

Linki zewnętrzne

[edytuj |edytuj kod]
Typyliczb naturalnych
zdefiniowane
jawnymi wzorami
algebraicznymi
jawnymi wzorami
przestępnymi
wzorami
rekurencyjnymi
sumą dzielników
faktoryzacją
(czynnikami
pierwszymi)
bezkwadratowe
złożone
inne
własnościami
zapisu dziesiętnego
typyliczb
pierwszych
inne typy liczb
naturalnych

Ciągi liczbowe
pojęcia
definiujące
ciągi ogólne
ciągi liczbowe
typy
ciągów
skończone
szeregi liczbowe
inne ciągi
nieskończone
ściśle
monotoniczne
inne
monotoniczne
inne
przykłady
ciągów
liczb
naturalnych
niemalejące
inne
inne
przykłady
twierdzenia
ogranicach
inne
powiązane
pojęcia
Encyklopedie internetowe (pojęcie matematyczne):
Źródło: „https://pl.wikipedia.org/w/index.php?title=Liczby_Mersenne’a&oldid=77070665”
Kategoria:
Ukryte kategorie:
[8]ページ先頭
©2009-2025 Movatter.jp