Bon allez, je vous dis tout :

Pour tout M(m) non premier, il a pour facteur 2 nombres premiers (une ou plusieurs paires de nombres premiers); l'un de forme 8x-1 et l'autre de forme 8y+1. De plus, ces nombres premiers sont de forme mz+1.

Code:
M(11) = 2047 =		23 * 89 =	 11*2+1 * 11*8+1 =	 3*8-1 * 11*8+1
M(23) = 8388607 =	47 * 178481 =	 23*2+1 * 23*7760+1 =	 6*8-1 * 22310*8+1
M(29) = 536870911 =	233 * 2304167 =	 29*8+1 * 29*79454+1 =	 288021*8-1 * 29*8+1

Ces cribleurs de Mersenne de forme 8x-1 et 8y+1 (que je nomme C- et C+) ont aussi une particularité. Leur produit a pour facteur 'm' et 3 :

Code:
M(11) = 3*8-1 * 11*8+1 =	3C- * 11C+	  => (3 * 11) Mod 11 = 0	=> *3		=> 3 Mod 3 = 0		=> *1
M(23) = 6*8-1 * 22310*8+1 =	6C- * 22310C+	  => (6 * 22310) Mod 23 = 0	=> *5820	=> 5820 Mod 3 = 0	=> *1940
M(29) = 29*8+1 * 288021*8-1 =	288021C- * 29C+	  => (29 * 288021) Mod 29 = 0	=> *288021	=> 288021 Mod 3 = 0	=> *96007

Donc, en résumé :

2^m-1 = ( 8x - 1 ) * ( 8y + 1) = ( mw + 1 ) * ( mz + 1)

Analysons 2^m-1 = ( mw + 1 ) * ( mz + 1) :

( mw + 1 ) * ( mz + 1) = 2^m-1
m²wz + mw + mz + 1 = 2^m-1
m(mwz + w + z) = 2^m-2
mwz + w + z = ( 2^m-2 ) / m

Maintenant, choisissons un nombre premier pour voir s'il est mersenne premier. Prenons 11
11*wz + w + z = ( 2^11-2 ) / 11
11*wz + w + z = 186
Il ne reste plus qu'à faire varier w pour voir si z est entier :
11*1*z + 1 + z = 186
12*z = 185
z = 185 / 12
si nous avions choisis w = 2, cela donnerait :
11*2*z + 2 + z = 186
23*z = 184
z = 184 / 23
La formule est donc ( (2^m - 2) - m ) / ( mn + 1 ) avec n pair allant de 2 à un certain nombre.

Mais puisque l'on sait aussi que ( 8x - 1 ) * ( 8y + 1) = ( mw + 1 ) * ( mz + 1), il faut trouver les bonnes 'corespondances' à notre formule ( (2^m - 2) - m ) / ( mn + 1 ).
Ce qui est très simple (en vous passant les détails) : regardez si 2m modulo 8 = 0 ou si (2m+2) modulo 8 = 0. Si c'est le cas, 50% de vos cribleurs de Mersenne se trouvent dans ce que j'appelle la branche des 2; sinon, ils font parti de la branche des 6. Les autres 50% des cribleurs se trouvent dans la branche des 8.

Exemple : M(11) = 2^11-1
11*2 = 22
22 Mod 8 <> 0
et 11*2+2 = 24
24 Mod 8 = 0
2^11-1; s'il n'est pas premier, a donc pour facteurs un cribleur de la branche des 2 et un cribleur de la branche des 8.

La branche des 2 est la suivante :
( 2^m - ( 2 + 8x )) / ( m * ( 2 + 8x ) + 1 )
x variant de 0 à un certain nombre
La branche des 8 est la suivante :
( 2^m - ( 8 + 8x )) / ( m * ( 8 + 8x ) + 1 )
x variant de 0 à un certain nombre

Si l'on testais 2^13-1, comme 13*2 Mod 8 <> 0 et (13*2+2) Mod 8 <> 0, on aurait eu la branche des 6 et des 8 :
La branche des 6 est la suivante :
( 2^m - ( 6 + 8x )) / ( m * ( 6 + 8x ) + 1 )
x variant de 0 à un certain nombre
La branche des 8 est la suivante :
( 2^m - ( 8 + 8x )) / ( m * ( 8 + 8x ) + 1 )
x variant de 0 à un certain nombre

Ajouté à tout ca, sachant qu'un Mersenne non premier a pour facteur deux nombres PREMIERS, le diviseur de chaque branche concerné doit etre premier. Soit on test la primalité du diviseur, soit on facilite le travail en écartant tout nombres finissant par 5 (car non premier).

Enfin, j'aimerais parler des C- et des C+. Ils se calculent plutot facilement. En voici un appercu (je rapelle qu'un C- est le 'x' de l'expression '8x-1' et qu'un C+ est le 'y' de l'expression '8y+1'):

Code:
C- : 1;3;4;6;9;10;13;16;19;21;24;25;28;30;33;34;39;45;46;48;54;55;58;60;61;63;75;76;79;81;90;91;93;94;103;105;108;111;114;115;121;123;124;129;130;133;136;138;144;153;154;160;163;165;166;171;175;178;180;181;184;186;189;193;195;196;198;201;208;220;223;228;229;231;234;235;244;250;255;258;261;264;268;276;280;286;289;294;298;300;303;306;313;318;319;324;331;333;334;336;339;340;346;349;360;361;363;366;375;378;385;390;396;399;409;415;418;420;424;426;433;439;441;445;448;451;453;454;459;465;466;471;478;481;483;489;490;493;496;501;510;514;516;520;529;534;541;549;553;556;558;565;571;573;574;580;583;585;588;594;595;598;600;604;609;613;615;618;619;621;625;628;630;636;640;646;654;660;663;669;675;676;679;684;685;688;690;691;699;703;705;706;714;718;723;724;726;730;735;738;741;751;756;760;768;769;775;781;783;784;786;789;793;795;796;819;825;826;835;838;840;849;853;858;859;864;870;871;873;874;880;885;888;891;894;895;901;906;919;936;945;948;949;951;955;961;963;966;970;978;985;990;991;994;1005;1011;1014;1021;
Code:
C+ : 9;11;29;42;75;110;117;161;179;201;215;225;239;261;305;324;371;407;431;507;522;525;537;551;564;590;635;651;711;717;761;794;795;819;857;941;969;999;1089;1095;1121;1221;1332;1367;1389;1397;1407;1457;1475;1505;1506;1509;1551;1557;1580;1605;1631;1667;1677;1817;1829;1862;1871;1877;1899;1905;1911;1976;2031;2045;2079;2091;2151;2217;2235;2255;2265;2315;2327;2406;2411;2537;2565;2601;2615;2627;2679;2685;2709;2714;2747;2837;2847;2877;2901;2921;2975;2979;3015;3041;3059;3119;3231;3239;3281;3329;3347;3356;3426;3537;3549;3582;3587;3591;3602;3629;3651;3729;3767;3837;3855;3879;3956;3965;3971;4011;4047;4089;4196;4205;4215;4277;4287;4289;4295;4355;4362;4370;4385;4431;4487;4526;4557;4566;4599;4665;4667;4692;4797;4841;4859;4970;5001;5019;5021;5030;5045;5054;5087;5105;5135;5145;5231;5261;5430;5435;5447;5465;5486;5562;5642;5645;5679;5717;5756;5805;5835;5846;5861;5877;5891;5895;5937;5957;5964;5967;5985;6035;6081;6119;6150;6162;6171;6177;6185;6225;6291;6297;6305;6407;6431;6449;6497;6531;6627;6639;6641;6650;
Vous remarquerez qu'il y a beaucoup plus de C- que de C+

suite dans la journée...