În matematică și mai precis în aritmetică , un număr Mersenne este un număr de forma 2 n - 1 (unde n este un număr natural diferit de zero), un număr prim Mersenne (uneori un număr prim Mersenne ), este deci un număr primul de acest formular. Aceste numere sunt numite după erudit religios și matematician francez al XVII - lea din secolul Marin Mersenne , dar în urmă cu aproape 2000 de ani, Euclid deja folosit pentru studiunumere perfecte .
Dacă un număr Mersenne 2 n - 1 este prim, neapărat n este prim, dar această condiție nu este suficientă: 2, 3, 5, 7 și 11 sunt prime, numerele Mersenne 2 2 - 1 = 3 , 2 3 - 1 = 7 , 2 5 - 1 = 31 și 2 7 - 1 = 127 sunt într-adevăr prime, dar numărul Mersenne 2 11 - 1 = 2047 = 23 × 89 nu este.
Există un test de primărie eficient pentru numerele Mersenne, testul de primărie Lucas-Lehmer , care face ca cele mai mari numere prime cunoscute să fie numere Mersenne. Numerele prime Mersenne sunt însă rare: 51 sunt cunoscute la începutul anului 2020. Cercetarea lor face obiectul unui proiect de calcul colaborativ, proiectul GIMPS . Nu știm dacă există o infinitate de numere prime Mersenne.
Numerele prime Mersenne sunt legate de numere perfecte , care sunt numere „egale cu suma divizorilor lor proprii ”. Această conexiune a motivat istoric studiul numerelor prime Mersenne. Din IV - lea secol î.Hr.. BC , Euclid a demonstrat că dacă M = 2 p - 1 este un număr prim, atunci M ( M + 1) / 2 = 2 p –1 (2 p - 1) este un număr perfect. Două milenii mai târziu, în secolul al XVIII- lea , Euler a dovedit că toți numerele perfecte de colegi au această formă. Nu se cunoaște niciun număr perfect ciudat.
Al n- lea număr Mersenne 2 n -1 este uneori notat cu M n = 2 n -1 ( n ∈ ℕ * ). Nu toate numerele Mersenne sunt prime, de exemplu M 4 = 2 4 - 1 = 15 = 3 × 5 . De fapt, de îndată ce n = kl este compus, M n = 2 kl - 1 este compus, deoarece 2 k - 1 , care este strict mai mare decât 1 dacă k este strict mai mare decât 1, este un divizor de 2 kl - 1 .
Un număr Mersenne M n = 2 n -1 poate fi deci prim numai dacă n este prim.
Conversa este falsă: chiar dacă n este prim, numărul Mersenne M n poate să nu fie prim. Cel mai mic contraexemplu este M 11 = 2047 = 23 × 89 .
Numerele Mersenne au următoarele proprietăți
P: M p este prim -: M p nu este prim Cyan: Mersenne a prevăzut Rose: el a prevăzut opusul | ||||||||
p | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
M p | P | P | P | P | - | P | P | P |
p | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 |
M p | - | - | P | - | - | - | - | - |
p | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
M p | - | P | - | - | - | - | - | P |
p | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 |
M p | - | - | - | P | - | - | P | - |
p | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
M p | - | - | - | - | - | - | - | - |
p | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
M p | - | - | - | - | - | - | - | - |
p | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 |
M p | - | - | - | - | - | - | - | - |
Dacă M n este prim, atunci și n . Marin Mersenne , un călugăr din ordinul Minimes la începutul XVII - lea secol , este autorul propunerii , care altfel ar fi demonstrat . De asemenea, oferă o listă a numerelor prime „Mersenne” până la exponentul 257, care se vor dovedi false: a inclus în mod eronat 67 și 257 și a omis 61, 89 și 107.
Reciproca este fals: M p poate fi compus în timp ce p este prim; cel mai mic contraexemplu este M 11 = 2047 = 23 × 89: 11 este prim, dar M 11 nu este, așa cum amintit din nou în 1732 de Euler , care menționează, că este și cazul p = 23, 83, 131, 179, 191 și 239.
Pentru ca M n să fie prim, n trebuie să fie prim, ceea ce simplifică deja căutarea numerelor prime Mersenne. Pentru a testa dacă un număr Mersenne M p (cu p prim) este prim, există o metodă comparativ foarte rapidă, dezvoltată inițial de Édouard Lucas în 1878 și îmbunătățită de Derrick Lehmer în anii 1930 . Datorită acestui test excepțional de simplu în comparație cu dimensiunea numerelor considerate că pentru o lungă perioadă de timp cele mai mari numere prime cunoscute au fost numerele prime Mersenne.
Primele patru numere prime ale lui Mersenne erau cunoscute din Antichitate. Al cincilea (2 13 - 1) a fost descoperit înainte de 1461 de către o persoană necunoscută. Următoarele două au fost găsite de Pietro Cataldi în 1588 . Mai mult de un secol mai târziu, în 1750 , Euler a mai găsit unul. Următorul în ordine cronologică (dar nu numerică) a fost găsit de Lucas în 1876 , apoi unul de Ivan Pervushin în 1883 . Alte două au fost găsite la începutul secolului XX de către RE Powers (în) în 1911 și 1914 .
Cercetarea lui Mersenne pentru numerele prime a fost revoluționată prin introducerea computerelor electronice. Prima identificare a unui număr Mersenne prin acest mijloc a avut loc la ora 22:0030 ianuarie 1952de un computer SWAC la Institutul de Analiză Numerică din campusul Universității din California Los Angeles , sub conducerea lui Derrick Lehmer, cu un program scris de Raphael Robinson .
A fost primul număr prim Mersenne identificat de 38 de ani. Următorul a fost găsit la mai puțin de două ore mai târziu de același computer, care a găsit încă trei în lunile următoare.
În decembrie 2018 , erau cunoscute 51 de numere prime Mersenne, cel mai mare fiind M 82 589 933 , care este, de asemenea, la aceeași dată cel mai mare număr prim cunoscut. La fel ca mulți dintre predecesorii săi, a fost descoperit printr-un calcul distribuit sub egida proiectului GIMPS , Great Internet Mersenne Prime Search (care înseamnă „căutare mare pe Internet a numerelor prime Mersenne”).
Nu știm dacă mulțimea numerelor prime Mersenne este finită sau infinită (dar presupunem că este infinită). În decembrie 2018 , erau cunoscute 51 de numere Mersenne prime (seria A000043 ( p ) și A000668 ( M p )).
Din punct de vedere istoric, acestea nu au fost întotdeauna descoperite în ordine crescătoare (exemple: al 12-lea, M 127 , al 29-lea M 4423 ...).
rang | p | M p | Valoarea M p în baza zece | Numărul de cifre din baza zece |
Data descoperirii | Descoperitor (i) |
---|---|---|---|---|---|---|
1 | 2 | M 2 | 3 | 1 | antichitate | observat (ca număr prim) de către matematicienii greci |
2 | 3 | M 3 | 7 | 1 | ||
3 | 5 | M 5 | 31 | 2 | ||
4 | 7 | M 7 | 127 | 3 | ||
5 | 13 | M 13 | 8.191 | 4 | Evul Mediu ( sec . XIII ) | Ibn Fallus (1194-1239) |
6 | 17 | M 17 | 131.071 | 6 | 1588 | Cataldi |
7 | 19 | M 19 | 524.287 | 6 | 1588 | Cataldi |
8 | 31 | M 31 | 2.147.483.647 | 10 | 1750 | Euler |
9 | 61 | M 61 | 2 305 843 009 213 693 951 | 19 | 1883 | Pervushin |
10 | 89 | M 89 | 618970019 ... 449562111 | 27 | 1911 | Puteri (ro) |
11 | 107 | M 107 | 162259276… 010288127 | 33 | 1914 | Puteri |
12 | 127 | M 127 | 170141183 ... 884105727 | 39 | 1876 | Lucas |
13 | 521 | M 521 | 686479766 ... 115057151 | 157 | 30 ianuarie 1952 | Robinson ( SWAC ) |
14 | 607 | M 607 | 531137992 ... 031728127 | 183 | 30 ianuarie 1952 | Robinson (SWAC) |
15 | 1.279 | M 1279 | 104079321 ... 168729087 | 386 | 25 iunie 1952 | Robinson (SWAC) |
16 | 2.203 | M 2203 | 147597991 ... 697771007 | 664 | 7 octombrie 1952 | Robinson (SWAC) |
17 | 2 281 | M 2281 | 446087557… 132836351 | 687 | 9 octombrie 1952 | Robinson (SWAC) |
18 | 3 217 | M 3217 | 259117086 ... 909315071 | 969 | 8 septembrie 1957 | Riesel ( BESK (ro) ) |
19 | 4.253 | M 4253 | 190797007 ... 350484991 | 1.281 | 3 noiembrie 1961 | Hurwitz ( IBM ) |
20 | 4.423 | M 4423 | 285542542 ... 608580607 | 1332 | 3 noiembrie 1961 | Hurwitz (IBM) |
21 | 9 689 | M 9689 | 478220278 ... 225754111 | 2 917 | 11 mai 1963 | Gillies (ro) ( ILLIAC II) |
22 | 9 941 | M 9941 | 346088282 ... 789463551 | 2 993 | 16 mai 1963 | Gillies (ILLIAC II) |
23 | 11,213 | M 11213 | 281411201… 696392191 | 3 376 | 2 iunie 1963 | Gillies (ILLIAC II) |
24 | 19 937 | M 19937 | 431542479 ... 968041471 | 6.002 | 4 martie 1971 | Tuckerman (în) (IBM) |
25 | 21.701 | M 21701 | 448679166… 511882751 | 6 533 | 30 octombrie 1978 | Noll (ro) și Nickel ( CDC ) |
26 | 23.209 | M 23209 | 402874115 ... 779264511 | 6.987 | 9 februarie 1979 | Noll (CDC) |
27 | 44,497 | M 44497 | 854509824… 011228671 | 13,395 | 8 aprilie 1979 |
Nelson (ro) și Slowinski (ro) ( Cray Research ) |
28 | 86.243 | M 86243 | 536927995 ... 433438207 | 25 962 | 25 septembrie 1982 | Slowinski (Cray) |
29 | 110.503 | M 110503 | 521928313 ... 465515007 | 33 265 | 28 ianuarie 1988 | Colquitt și Welsh ( NEC ) |
30 | 132.049 | M 132049 | 512740276… 730061311 | 39.751 | 19 septembrie 1983 | Slowinski (Cray) |
31 | 216.091 | M 216091 | 746093103… 815528447 | 65.050 | 1 st septembrie 1985 | Slowinski (Cray) |
32 | 756.839 | M 756839 | 174135906 ... 544677887 | 227 832 | 19 februarie 1992 | Slowinski și Gage |
33 | 859 433 | M 859433 | 129498125 ... 500142591 | 258.716 | 10 ianuarie 1994 | Slowinski și Gage |
34 | 1.257.787 | M 1257787 | 412245773… 089366527 | 378.632 | 3 septembrie 1996 | Slowinski și Gage |
35 | 1.398.269 | M 1398269 | 814717564 ... 451315711 | 420 921 | 13 noiembrie 1996 | GIMPS / Joel Armengaud |
36 | 2 976 221 | M 2976221 | 623340076… 729201151 | 895 932 | 24 august 1997 | GIMPS / Gordon Spence |
37 | 3.021.377 | M 3021377 | 127411683 ... 024694271 | 909.526 | 27 ianuarie 1998 | GIMPS / Roland Clarkson |
38 | 6.972.593 | M 6972593 | 437075744 ... 924193791 | 2.098.960 | 1 st iunie 1999 | GIMPS / Nayan Hajratwala |
39 | 13.466.917 | M 13466917 | 924947738 ... 256259071 | 4.053.946 | 14 noiembrie 2001 | GIMPS / Michael Cameron |
40 | 20.996.011 | M 20996011 | 125976895 ... 855682047 | 6 320 430 | 17 noiembrie 2003 | GIMPS / Michael Shafer |
41 | 24.036.583 | M 24036583 | 299410429 ... 733969407 | 7 235 733 | 15 mai 2004 | GIMPS / Josh Findley |
42 | 25 964 951 | M 25964951 | 122164630 ... 577077247 | 7 816 230 | 18 februarie 2005 | GIMPS / Martin Nowak |
43 | 30 402 457 | M 30402457 | 315416475 ... 652943871 | 9.152.052 | 15 decembrie 2005 | GIMPS / Cooper și Boone |
44 | 32.582.657 | M 32582657 | 124575026 ... 053967871 | 9.808.358 | 4 septembrie 2006 | GIMPS / Cooper și Boone |
45 | 37 156 667 | M 37156667 | 202254405 ... 308220927 | 11 185 272 | 6 septembrie 2008 | GIMPS / Elvenich |
46 | 42 643 801 | M 42643801 | 169873516… 562314751 | 12 837 064 | 12 aprilie 2009 | GIMPS / Odd Magnar Strindmo |
47 | 43 112 609 | M 43112609 | 316470269 ... 697152511 | 12 978 189 | 23 august 2008 | GIMPS / Smith |
48? | 57 885 161 | M 57885161 | 581887266… 724285951 | 17 425 170 | 25 ianuarie 2013 | GIMPS / Cooper |
49? | 74 207 281 | M 74207281 | 300376418… 086436351 | 22 338 618 | 7 ianuarie 2016 | GIMPS / Cooper |
50? | 77 232 917 | M 77232917 | 467333183 ... 762179071 | 23 249 425 | 3 ianuarie 2018 | GIMPS / Jonathan Pace |
51? | 82.589.933 | M 82589933 | 148894445 ... 217902591 | 24 862 048 | 7 decembrie 2018 | GIMPS / Patrick Laroche |
Noul mici non-prime Mersenne , dar indicii timpurii (de potrivire între 1 st și 9 - lea numărul de numere prime Mersenne, cunoscut la sfârșitul XIX - lea lea ) sunt:
N o | p | M p | Valoarea M p în baza zece |
Numărul de cifre din baza zece |
Descompunere |
---|---|---|---|---|---|
1 | 11 | M 11 | 2.047 | 4 | 23 × 89 |
2 | 23 | M 23 | 8 388 607 | 7 | 47 × 178 481 |
3 | 29 | M 29 | 536 870 911 | 9 | 233 × 1.103 × 2.089 |
4 | 37 | M 37 | 137 438 953 471 | 12 | 223 × 616 318 177 |
5 | 41 | M 41 | 2 199 023 255 551 | 13 | 13 367 × 164 511 353 |
6 | 43 | M 43 | 8 796 093 022 207 | 13 | 431 × 9.719 × 2.099.863 |
7 | 47 | M 47 | 140 737 488 355 327 | 15 | 2.351 × 4.513 × 13.264.529 |
8 | 53 | M 53 | 9 007 199 254 740 991 | 16 | 6.361 × 69.431 × 20.394.401 |
9 | 59 | M 59 | 576 460 752 303 423 487 | 18 | 179 951 × 3 203 431 780 337 |
Numărul M 67 , egal cu 147 573 952 589 676 412 927 , a apărut în lista originală a Mersenne; cu toate acestea, Lucas a arătat în 1876 că acest număr nu era prim, fără a putea totuși să-și expună factorii. Factorizarea acestui număr (193.707.721 x 761.838.257.287) a fost determinată de Frank Nelson Cole în 1903.
Numerele Mersenne (prime sau nu) sunt răspunsurile din baza 2. Secvența răspunsurilor din baza b este secvența lui Lucas U ( b + 1, b ). Cu toate acestea, orice secvență Lucas U ( P , Q ) cu P și Q prime între ele are o divizibilitate puternică . Prin același raționament ca și pentru succesiunea numerelor Mersenne (a se vedea mai sus ), o condiție necesară (dar nu suficientă) pentru ca al n -lea termen al unei astfel de secvențe să fie prim este, prin urmare, că n este, de asemenea, prim .
Numerele prime Solinas sunt numere prime de forma p = f (2 k ) unde f este un polinom unitar cu coeficienți întregi cu „greutate de reducere modulară” mică (o condiție tehnică destinată reducerii modulului p sunt rapide și care, pentru simplitate, este uneori înlocuit cu: coeficienții non-zero ai lui f sunt puțini și egali ± 1). Solinas oferă o serie de exemple, dintre care primul este f ( t ) = t - 1, de „greutate” 1 (care corespunde numerelor Mersenne) și ultimul este f ( t ) = t 4 - t 3 + t 2 + 1, de „greutate” 4, dar care include și f ( t ) = t d - t d –1 + t d –2 - ... + (–1) d , de „greutate” 3.
Deoarece numerele Mersenne sunt repunitele din baza 2, scrierea lor binară nu include niciunul 0. În mod similar, putem studia în bazele superioare numerele prime a căror scriere nu are o anumită cifră. S-a dovedit în 2019 că există o infinitate de numere prime a căror expansiune în baza 10 nu include niciuna dintre cifrele de la 0 la 9.
unde el