Numărul prim al lui Mersenne

În matematică, un prim Mersenne este un număr prim care este unul mai mic decât o putere de două . Prin urmare, poate fi exprimat ca:

M_{p}=2^{p}-1,

{\ displaystyle M_ {p} = 2 ^ {p} -1,}

{\ displaystyle M_ {p} = 2 ^ {p} -1,}

cu $p$ ${\ displaystyle p}$ $p$ prim întreg pozitiv . Acest număr $p$ ${\ displaystyle p}$ $p$ este uneori denumit exponent Mersenne (succesiunea A000043 în OEIS ). Rețineți că $2^{11}-1=2047=23\cdot 89$ ${\ displaystyle 2 ^ {11} -1 = 2047 = 23 \ cdot 89}$ ${\ displaystyle 2 ^ {11} -1 = 2047 = 23 \ cdot 89}$ nu este prim și, prin urmare, nu toate numerele prime corespund unui exponent Mersenne, ci numai acelora pentru care $M_{p}=2^{p}-1$ ${\ displaystyle M_ {p} = 2 ^ {p} -1}$ ${\ displaystyle M_ {p} = 2 ^ {p} -1}$ este, de asemenea, primul.

Uneori în definiția lui Mersenne a numărului prim $M_{n}$ ${\ displaystyle M_ {n}}$ $M_n$ numai indicele este necesar a priori $n$ ${\ displaystyle n}$ $n$ fii primul. Echivalența celor două definiții rezultă din faptul că dacă $M_{n}$ ${\ displaystyle M_ {n}}$ ${\ displaystyle M_ {n}}$ este mai întâi, apoi și $n$ ${\ displaystyle n}$ $n$ trebuie să fie primul, așa cum se vede ușor din identitate

2^{ab}-1=(2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a}+\cdots +2^{(b-1)a}\right).

{\ displaystyle 2 ^ {ab} -1 = (2 ^ {a} -1) \ cdot \ left (1 + 2 ^ {a} + 2 ^ {2a} + 2 ^ {3a} + \ cdots + 2 ^ {(b-1) a} \ dreapta).}

{\ displaystyle 2 ^ {ab} -1 = (2 ^ {a} -1) \ cdot \ left (1 + 2 ^ {a} + 2 ^ {2a} + 2 ^ {3a} + \ cdots + 2 ^ {(b-1) a} \ dreapta).}

În general, un număr ca $M_{n}=2^{n}-1$ ${\ displaystyle M_ {n} = 2 ^ {n} -1}$ ${\ displaystyle M_ {n} = 2 ^ {n} -1}$ se numește „număr Mersenne” (chiar și atunci când nu este un prim Mersenne). Mai multe proprietăți ale factorilor primi ai $M_{p}$ ${\ displaystyle M_ {p}}$ $M_p$ compus cu $p$ ${\ displaystyle p}$ $p$ primul. De exemplu (și Fermat a fost primul care a evidențiat și a folosit această proprietate) se poate arăta că fiecare factor este prim $M_{p}$ ${\ displaystyle M_ {p}}$ $M_p$ trebuie să fie ca. $2kp+1$ ${\ displaystyle 2kp + 1}$ ${\ displaystyle 2kp + 1}$ cu $k$ ${\ displaystyle k}$ $k$ număr întreg pozitiv ^[1] .

Numerele prime Mersenne sunt numite după matematicianul francez Marin Mersenne ( 1588 - 1648 ). Mersenne a întocmit o listă a primelor de acest tip luând în considerare toate valorile $n$ ${\ displaystyle n}$ $n$ până la $n=257$ ${\ displaystyle n = 257}$ ${\ displaystyle n = 257}$ . Cu toate acestea, această listă conținea câteva erori: a inclus $M_{67}$ ${\ displaystyle M_ {67}}$ ${\ displaystyle M_ {67}}$ Și $M_{257}$ ${\ displaystyle M_ {257}}$ ${\ displaystyle M_ {257}}$ (care nu sunt prime), în timp ce nu au apărut $M_{61}$ ${\ displaystyle M_ {61}}$ ${\ displaystyle M_ {61}}$ , $M_{89}$ ${\ displaystyle M_ {89}}$ ${\ displaystyle M_ {89}}$ Și $M_{107}$ ${\ displaystyle M_ {107}}$ ${\ displaystyle M_ {107}}$ (care sunt prime).

Primele douăsprezece numere prime Mersenne sunt:

M_{2}=2^{2}-1=3

{\ displaystyle M_ {2} = 2 ^ {2} -1 = 3}

{\ displaystyle M_ {2} = 2 ^ {2} -1 = 3}

M_{3}=2^{3}-1=7

{\ displaystyle M_ {3} = 2 ^ {3} -1 = 7}

{\ displaystyle M_ {3} = 2 ^ {3} -1 = 7}

M_{5}=2^{5}-1=31

{\ displaystyle M_ {5} = 2 ^ {5} -1 = 31}

{\ displaystyle M_ {5} = 2 ^ {5} -1 = 31}

M_{7}=2^{7}-1=127

{\ displaystyle M_ {7} = 2 ^ {7} -1 = 127}

{\ displaystyle M_ {7} = 2 ^ {7} -1 = 127}

M_{13}=2^{13}-1=8191

{\ displaystyle M_ {13} = 2 ^ {13} -1 = 8191}

{\ displaystyle M_ {13} = 2 ^ {13} -1 = 8191}

M_{17}=131071

{\ displaystyle M_ {17} = 131071}

{\ displaystyle M_ {17} = 131071}

M_{19}=524287

{\ displaystyle M_ {19} = 524287}

{\ displaystyle M_ {19} = 524287}

M_{31}=2147483647

{\ displaystyle M_ {31} = 2147483647}

{\ displaystyle M_ {31} = 2147483647}

M_{61}=2305843009213693951

{\ displaystyle M_ {61} = 2305843009213693951}

{\ displaystyle M_ {61} = 2305843009213693951}

M_{89}=618970019642690137449562111

{\ displaystyle M_ {89} = 618970019642690137449562111}

{\ displaystyle M_ {89} = 618970019642690137449562111}

M_{107}=162259276829213363391578010288127

{\ displaystyle M_ {107} = 162259276829213363391578010288127}

{\ displaystyle M_ {107} = 162259276829213363391578010288127}

M_{127}=170141183460469231731687303715884105727

{\ displaystyle M_ {127} = 170141183460469231731687303715884105727}

{\ displaystyle M_ {127} = 170141183460469231731687303715884105727}

Numerele prime Mersenne sunt legate de numere perfecte . În secolul al IV-lea î.Hr. Euclid a dovedit că dacă $M_{n}$ ${\ displaystyle M_ {n}}$ $M_n$ este un număr prim, atunci ${M_{n}\cdot (M_{n}+1) \over 2}=2^{n-1}\cdot (2^{n}-1)$ ${\ displaystyle {M_ {n} \ cdot (M_ {n} +1) \ over 2} = 2 ^ {n-1} \ cdot (2 ^ {n} -1)}$ ${\ displaystyle {M_ {n} \ cdot (M_ {n} +1) \ over 2} = 2 ^ {n-1} \ cdot (2 ^ {n} -1)}$ este un număr perfect .

În secolul al XVIII-lea, Euler a dovedit că toate numerele pare perfecte au această formă. Nu se cunosc numere perfecte ciudate și este posibil, de asemenea, să nu existe.

Apariția computerelor electronice a accelerat foarte mult descoperirea primului Mersenne. Primele douăsprezece prime Mersenne au fost descoperite înainte de secolul al XX-lea . La sfârșitul mileniului, cele mai vechi Mersenne cunoscute erau 38; astăzi, însă, sunt cunoscute 51 și cele mai recente șaptesprezece au fost descoperite în cadrul GIMPS , Great Internet Mersenne Prime Search , o inițiativă care exploatează resursele disponibile ale mii de computere din rețea pentru a le căuta pe primele din Mersenne. Testul de primărie utilizat de GIMPS este testul Lucas-Lehmer, care este mult mai rapid decât testele generice cu același ordin de mărime ca număr; de aceea, înregistrările celor mai mari primi cunoscuți au fost mult timp primii Mersenne. Cel mai mare număr prim cunoscut (începând cu 21 decembrie 2018) este $M_{82589933}$ ${\ displaystyle M_ {82589933}}$ ${\ displaystyle M_ {82589933}}$ . Are peste 24 de milioane de zecimale și a fost găsit și în domeniul GIMPS:

M_{82589933}=2^{82589933}-1

{\ displaystyle M_ {82589933} = 2 ^ {82589933} -1}

{\ displaystyle M_ {82589933} = 2 ^ {82589933} -1}

^[2]

Dacă sunt scrise în baza 2 , toate primele Mersenne sunt prime repunitate , adică sunt reprezentate prin șiruri de p cifre unitare, unde p este exponentul prim Mersenne. În exemplele de mai jos, indicele indică baza în care este exprimat numărul:

3 ₁₀ = 11 ₂

7 ₁₀ = 111 ₂

31 ₁₀ = ₁₁ 111 ₂

127 ₁₀ = 1111111 ₂

8191 ₁₀ = 1111111111111 ₂ .

Rețineți că această proprietate este posedată atunci când 1 este scăzut din toate puterile lui 2 având un număr prim ca exponent. Practic, toți candidații la primii Mersenne (numiți pur și simplu „numere Mersenne” așa cum s-a menționat mai sus) în notație binară sunt repuneri prime.

Se poate observa derulând lista de mai jos, că, în afară de 3, toate primele Mersenne se termină cu 1 sau 7. Acest lucru se datorează faptului că puterile lui 2 se termină ciclic cu 2, 4, 8, 6, când exponentul este respectiv de forma 1 + 4k, 2 + 4k, 3 + 4k și 4 + 4k (k număr natural pozitiv). Din acest motiv, numai puterile lui 2 care se termină în 2 și 8 au exponenți de forma 1 + 4k și 3 + 4k, adică au exponenți impari, în timp ce cei care se termină în 4 și 6 au exponenți chiar. În cele din urmă, având în vedere că într-un moment de Mersenne $2^{p}-1$ ${\ displaystyle 2 ^ {p} -1}$ $2 ^ {p} -1$ , trebuie să fie $p$ ${\ displaystyle p}$ $p$ numărul prim, acesta trebuie să fie impar, cu excepția cazului în care $p=2$ ${\ displaystyle p = 2}$ $p = 2$ corespunzând singurului număr de Mersenne care se termină cu 3 (numărul 3 de fapt).

Primele Mersenne, scrise la baza 2, sunt și primele palindromice , primele permutabile și primele Gauss .

Lista numerelor prime ale lui Mersenne

#	p	M _p	Cifrele din M _p	Data descoperirii	Descoperitor
1	2	3	1	Antichitate	Necunoscut
2	3	7	1	Antichitate	Necunoscut
3	5	31	2	Antichitate	Necunoscut
4	7	127	3	Antichitate	Necunoscut
5	13	8191	4	1456	Necunoscut
6	17	131071	6	1588	Cataldi
7	19	524287	6	1588	Cataldi
8	31	2147483647	10	1772	Euler
9	61	2305843009213693951	19	1883	Pervushin
10	89	618970019642690137449562111	27	1911	Puteri
11	107	162259276829213363391578010288127	33	1914	Puteri
12	127	170141183 ... 884105727	39	1876	Lucas
13	521	686479766 ... 115057151	157	30 ianuarie 1952	Robinson
14	607	531137992 ... 031728127	183	30 ianuarie 1952	Robinson
15	1.279	104079321 ... 168729087	386	25 iunie 1952	Robinson
16	2.203	147597991 ... 697771007	664	7 octombrie 1952	Robinson
17	2.281	446087557… 132836351	687	9 octombrie 1952	Robinson
18	3.217	259117086 ... 909315071	969	8 septembrie 1957	Riesel
19	4.253	190797007 ... 350484991	1281	3 noiembrie 1961	Hurwitz
20	4.423	285542542 ... 608580607	1.332	3 noiembrie 1961	Hurwitz
21	9.689	478220278 ... 225754111	2.917	11 mai 1963	Gillies
22	9.941	346088282 ... 789463551	2.993	16 mai 1963	Gillies
23	11.213	281411201… 696392191	3.376	2 iunie 1963	Gillies
24	19.937	431542479 ... 968041471	6.002	4 martie 1971	Tuckerman
25	21.701	448679166… 511882751	6.533	30 octombrie 1978	Noll și Nickel
26	23.209	402874115 ... 779264511	6.987	9 februarie 1979	Noll
27	44,497	854509824… 011228671	13,395	8 aprilie 1979	Nelson și Slowinski
28	86.243	536927995 ... 433438207	25.962	25 septembrie 1982	Slowinski
29	110.503	521928313 ... 465515007	33.265	28 ianuarie 1988	Colquitt și Welsh
30	132.049	512740276… 730061311	39.751	20 septembrie 1983	Slowinski
31	216.091	746093103… 815528447	65.050	6 septembrie 1985	Slowinski
32	756.839	174135906 ... 544677887	227,832	19 februarie 1992	Slowinski și Gage în Harwell Lab Cray-2
33	859.433	129498125 ... 500142591	258 716	10 ianuarie 1994	Slowinski și Gage
34	1.257.787	412245773… 089366527	378,632	3 septembrie 1996	Slowinski și Gage
35	1.398.269	814717564 ... 451315711	420.921	13 noiembrie 1996	GIMPS / Joel Armengaud (PC Pentium 90)
36	2.976.221	623340076… 729201151	895.932	24 august 1997	GIMPS / Gordon Spence (PC Pentium 100)
37	3.021.377	127411683 ... 024694271	909.526	27 ianuarie 1998	GIMPS / Roland Clarkson (Pentium 200)
38	6.972.593	437075744 ... 924193791	2.098.960	1 iunie 1999	GIMPS / Nayan Hajratwala (Pentium II 350)
39	13.466.917	924947738 ... 256259071	4.053.946	14 noiembrie 2001	GIMPS / Michael Cameron (PC AMD T-Bird de 800 MHz)
40	20.996.011	125976895 ... 855682047	6.320.430	17 noiembrie 2003	GIMPS / Michael Shafer (computer Dell Dimension Pentium 4 2 GHz)
41	24.036.583	299410429 ... 733969407	7.235.733	15 mai 2004	GIMPS / Josh Findley (PC Windows XP de 2,4 GHz Pentium 4)
42	25.964.951	122164630 ... 577077247	7.816.230	18 februarie 2005	GIMPS / Martin Nowak (PC Windows XP 2,4 GHz Pentium 4)
43	30.402.457	315416475 ... 652943871	9.152.052	15 decembrie 2005	GIMPS / Curtis Cooper și Steven Boone
44	32.582.657	124575026 ... 053967871	9.808.358	4 septembrie 2006	GIMPS / Curtis Cooper și Steven Boone
45	37.156.667	202254406… 308220927	11.185.272	6 septembrie 2008	GIMPS / Hans-Michael Elvenich, George Woltman, Scott Kurowski și colab
46	42.643.801	169873516… 562314751	12,837,064	12 aprilie 2009	GIMPS / Odd M. Strindmo
47	43.112.609	316470269 ... 697152511	12.978.189	23 august 2008	GIMPS / Edson Smith, George Woltman, Scott Kurowski și colab
48? ^[3]	57.885.161	581887266… 724285951	17.425.170	25 ianuarie 2013	GIMPS / Curtis Cooper, George Woltman, Scott Kurowski și colab
49? ^[3]	74.207.281	300376418084 ... 391086436351	22.338.618	7 ianuarie 2016	GIMPS / Curtis Cooper
50? ^[3]	77.232.917	467333183359… 069762179071	23.249.425	26 decembrie 2017	GIMPS / Jonathan Pace
51? ^[3]	82.589.933	148894445742 ... 325217902591	24.862.048	7 decembrie 2018	GIMPS / Patrick Laroche

Notă

^ Mauro Fiorentini - Mersenne (numere de)
^ Raportul GIMPS Milestones , pe mersenne.org . Adus pe 21 decembrie 2018 .
^ ^a ^b ^c ^d Nu se știe dacă există și alte prime Mersenne între 47 (M43112609) și 51 (M82589933), iar numerotarea tabelului este, prin urmare, provizorie în partea sa finală. Primii Mersenne nu au fost întotdeauna descoperiți în ordine crescătoare. De exemplu, al 29-lea prim al lui Mersenne a fost descoperit după 30 și 31. În mod similar, al 47-lea a fost urmat de alte două numere mai mici, unul descoperit două săptămâni mai târziu și celălalt 8 luni mai târziu. GIMPS Milestones Report , pe mersenne.org . Adus pe 2 ianuarie 2019 .