nombre de Mersenne

[leg]

pole:Pour trouver a et b, tu factorise 2^p-1 et pas (2^p-1)-1
c'est l'inverse car tu connais déja certain facteur de (2^p-1)-1 en générale tu connais 3 et l'exposant et (si il se termine par 5, tu rajoutes 5) dans l'exemple cité
3 et 23 et tu sais que le reste est composé 60787 = (a+b) (a-b) = a² - b² , tu as un premiers indice 8388607/60787= 138,..que tu pourra utiliser pour retrouver A et B des que tu as factoriser 60787
=89*683 ce qui donne a= 386, b = 297
ase trouve a une certaine distance de A ainsi que: b vers B tu peux commencer avec 138*297 = 40986 = B
Mq = 8388607 + B² = 1688240803 et racine carré pour connaître A;
soit 41088,207, cela ne te donne pas encore la valeur de A et de B
mais tu obtiens une information :A - B = 102, or 102 serait le plus petit facteur au maximum de MQ soit tu continus avec A de plus en plus grand , 'c'est à dire 200 * 297, 300 * 297 pour te rapprocher du possible A soit tu parts de 29 et tu remontes vers 102.
pour M 29,= 536870911, (2^(p -1)-1 / 2 te donne 3.5.29 et 43*14351 = 617093 ; M29 /(617093*5) = 170 environ

a = 7197 , b = 7154; b*170 =1216180
B² + MQ = A² et racine carrée = A = 1216400,7
A - B = 220.7 le facteur P , c'est 223

en résumé , on trouve a et b et on sait qu'il y a un indice multiplicateur pour remonter Sur A ET B quelque soit cet indice,il nous donne déjà l'information, de la valeur du facteur P divisant Mq; car ce facteur P n'est autre que la différence entre A et B.
pour cet EX, A=1152200; B = 1151967;
B/b= 161,024 ,A/a = 160,09 ; A/b = 161.056.

bien sur il faut affiner cela , et si ce couple a et b est unique il est évident que Mq est premier ! de plus le couple a,b est toujours < A,B
on ne prend que les facteur, superieur a 3 et 5, et différent de l'exposant si il y ya le facteur 5 pour recherché une aproximation de l'indice on multiplie le reste par 5 comme je l'ai fait pour M29 sinon l'indice serait trop éloigné.
je pense que tu dois pouvoir formuler cela beaucoup mieux que moi et en tirer quelque chose de trés interressant A+.
-----

[leg]

bonjour a tous .
Je reviens sur la question posé par Pole: comment tu factorises simplement le "résidu" de 2^(p -1) - 1, en ne connaissant que l'exposant, 3, et ou 5;( je reprend tout depuis le début)

Je pensais que cette formule toute bête était connue. je n'ai pas fait de recherche a ce sujet, car il s'agit d'une méthode de Factorisation en connaissant au moins deux facteurs P ce qui est le cas dans les nombres de Mersenne pour :
2^(p -1) - 1.

mais rien n'empèche de l'étendre. et j'aimerai votre avis.

Pour trouver a et b, on factorise : de façon simple. 2^(p – 1) -1

Factorisation de : (2^p-1)-1

On connais déjà un certain facteur de (2^p-1)-1 ; en générale 3 et l'exposant et (si il se termine par 5, on rajoute 5), dans l'exemple cité :

2^23 -1 = 8388607 et (Mq – 1)/2 = 4194303 ce qui donne déjà : 2 facteurs P
3 et 23 et 60787 est composé !

Or, (2^p) - 2 = (U² - V²) / 2 et, pour V = 2 ; U et V s’obtiennent avec les facteurs de :
(Mq – 1)/2, pour cette exemple 4194303.

Question peut on factoriser facilement ce produit, oui en principe.
Connaissant 3 et 23, il nous faut un troisième facteur.

(Mq – 1) * 2 = ((2^p) -2)* 2 = U² -V², donc comme V = 2, U² = 2² + (2^p * 2); par conséquent, U = √U².

Exemple : 8388606 * 2 = 16777212, et + 4 = U², soit √16777216 = U = 4096 et bien sûr, 4096 / 2 = 2048 ce qui donne : v’ = 2048 – 1 ; et u’ = 2048 + 1, qui sont divisibles par 23 et 3, 2047 / 23 = 89 ; 2049 / 3 = 683 . les deux derniers facteur P du résidu.

On sait que le reste 60787 est composé = (a+b) (a-b) = a² - b².

Ceci va nous donner un premiers indice : 8388607/60787= 138,xxx que l’on pourra utiliser pour retrouver A et B des que 60787 a été factorisé = 89*683 ;
Et (683 + 89) / 2= 386 ; et 386 – 89 = 297.


ce qui donne a= 386, b = 297 ; a < A et b < B
a se trouve a une certaine distance de A, ainsi que: b vers B ; on peut commencer avec 138*297 = 40986 = ≈B
Mq = 8388607 + B² = 1688240803 et racine carré pour connaître A;
soit 41088,207, cela ne donne pas encore la valeur de A et de B
mais on a une information :A - B = 102. Or 102, serait le plus petit facteur au maximum de MQ soit on continu avec A de plus en plus grand, 'c'est à dire 200 * 297, 300 * 297 pour se rapprocher du possible A soit on part de 29 et on remonte vers 102.

pour M 29,= 536870911, (536870910 *2) + 4 = U² ; U = 32768 ;
u’ = 16385 et v’ = 16383 . qui sont divisible par 3,5 et 29 ce qui permet la factorisation du résidu!

16385/5 = 3277 et / 29 = 113. 16383 /3 = 5461 il reste 5461 a factoriser.( mais on peut composer a et b avec 113 et 5461; ce qui donne :2787 et 2674; cela nous indiquera la limite du facteur p divisant Mq si il est composé.)

(2^(p -1)-1 / 2, donne 3.5.29 et 43*14351 = 617093 ; et 14351 = 113*127

M29 /(617093*5) = 170 environ,( pour être le plus prés de l’indice on utilise tous les facteurs sauf l’exposant est 3)

a = 7197 , b = 7154; b*170 =1216180
B² + MQ = A² et racine carrée = A = 1216400,7
A - B = 220.7 le facteur P , c'est 223

En résumé :
1) on factorise de façon très simple [2^(p-1) -1] /2 !

2) on trouve a et b et on sait qu'il y a un indice multiplicateur pour remonter Sur A ET B quelque soit cet indice,il nous donne déjà l'information, de la valeur du facteur P divisant Mq; car ce facteur P n'est autre que la différence entre A et B.
pour cet EX, A=1152200; B = 1151967;
B/b= 161,024 ,A/a = 160,09 ; A/b = 161.056.

[invite3d7be5ae]

des que tu as factoriser 60787=89*683

La factorisation, c'est long.
Pour M_q, il faut factoriser M_q-1/3/q. Pour q~=
10 000 000, il y a entre 7 et 8 chiffres en moins.
Le gain n'est pas important.

[invite3d7be5ae]

Oups, je n'ai pas vu ton nouveau message.

[SPH]

J'ai besoin de vos lumieres car de mon point de vue, je sais ce que j'ai trouvé. Mais peut etre que VOTRE point de vue pourrait etre different du mien.
Alors, réunissez vos competences et dites moi ce que ces nombres premiers ont en commun; que n'ont pas les autres np (ceux qui sont differents de ceux ci et qui sont inferieur a 101) :

3; 5; 11; 13; 19; 29; 37; 53; 59; 61; 67; 83; 101

[leg]

la seule chose que je vois, aucune différence de 4 ou d'un multiple de 4 entre ces nombres p c'est 2 ou K*6 ce qui est génant c'est qu'il y est une différence de 10 =19 a 29.mais cela n'apportera strictement rien.

[leg]

sph c'est une blague ou une cole?
1+2+3 = le 5 èm, puis 2+3+4 = 6éme, ensuite cela se décale ce qui en gros donne: la somme de trois premier = un quatrième ...

[invite3d7be5ae]

Une colle, et je ne trouve pas.
Pour ta réponse, faux : 11+13+19=x3 alors qu'il y a 37 à la place.

Je remarque que dans les écarts entre de P qui se suivent, c'est souvent 6.

[SPH]

hmmmm ok. Apparement, il n'y a aucune logique en dehors de celle que je possede. (je bosse encore et je vous dirais tout en temps voulu)

[invite3d7be5ae]

La somme de 2 nombre consécutifs : 8, 16, 24, 32, 48, 66, 90, 112, 120, 128, 150, 184. Or le début est multiple de 8.
Si on prend les écarts : 8, 8, 8, 16, 18, 24, 22, 8, 8, 22, 34.
Encore des multiples de 8.

[SPH]

La somme de 2 nombre consécutifs : 8, 16, 24, 32, 48, 66, 90, 112, 120, 128, 150, 184. Or le début est multiple de 8.
Si on prend les écarts : 8, 8, 8, 16, 18, 24, 22, 8, 8, 22, 34.
Encore des multiples de 8.

Ha ouai, pas bete, j'avais pas vu. Mais est-ce systematique !!?!
Faudra que je regarde par rapport aux NP que j'ai mis de coté

[SPH]

Pole: ca y est, je viens de trouver comment savoir si X est premier sans connaitre les precedents NP !!

[leg]

j'espère que ce n'est pas un

et indique le temps que cela prend pour un Premier assez grand,
ou pour extraire une série de premiers
A+

[invitecf787e7b]

bonjour,
sph,
ces nombres ne divisent que 2^(p-1)-1 avec p premier , donc il ne seront jamais des diviseurs de
2^p-1 (avec p premier) lorsqu'ils sont composés ;
exemple 19 divise 2^18-1 donc il divisera tous les 2^18a-1 idem pour les autres )
voila
bon courage jeune homme

[SPH]

j'espère que ce n'est pas un

et indique le temps que cela prend pour un Premier assez grand,
ou pour extraire une série de premiers
A+

Le temps que je met serait moins grand que le temps que mettent nimporte quel programme actuellement si et seulement si mon algo est programmé par la meme equipe.
Je dis cela car j'ai beau coder mon algo, je ne peux pas lutter contre l'optimisation d'un programme ecrit par une equipe de programmeur.

[GuYem]

La somme de 2 nombre consécutifs : 8, 16, 24, 32, 48, 66, 90, 112, 120, 128, 150, 184. Or le début est multiple de 8.
Si on prend les écarts : 8, 8, 8, 16, 18, 24, 22, 8, 8, 22, 34.
Encore des multiples de 8.

Hein? (

[invite3d7be5ae]

Je n'ai pas dit qu'il n'y avait que des multiples de 8.
Mais il y en a quand même 7.

[inviteb0cf188d]

Bonjour,
Quelqu'un pourrait résumer cette discussion sur les nombres de Mersenne ? 13 pages, c'est beaucoup trop à relire.
Ah, j'oubliais : merci de fournir des preuves (mathématiques) et une évaluation de la complexité des algorithmes.
Et (si possible) en LaTeX, que les formules soient lisibles.

Exercice : Prouver que [1]
(Alors, est premier s'il y a un seul couple (x,y) solution de [1]).

Merci,
Tony

[invite3d7be5ae]

Je ne connais pas Latex. Tu pourrais m'expliquer par mp?
Merci.

[inviteb0cf188d]

"... par mp" ??? Je ne comprends pas.

Tu as vraiment 12 ans ?

LaTeX : c'est un formidable outil permettant de faire de superbe documents. C'est le seul outil permettant d'écrire de beaux et clairs papiers mathématiques. Ce forum permet d'intégrer du TeX. Il suffit d'entourer la formule par : \[tex\] et \[/tex\] (tu enlèves les \ pour que cela marche.) .
Ce forum ne permet pas de voir le code source du TeX que tu vois.
Par contre, celui-ci le permet : http://www.physicsforums.com/showthread.php?t=88025
Clique sur la forumule mathématique.

Voici un peu de doc sur TeX : www.maths.bris.ac.uk/~maxmg/maths
Une autre : http://www.mersenneforum.org/mimetex.htm

Si l'anglais est un pb, en français : http://tex.loria.fr/general/apprends-latex.pdf

Pour faire de vrais documents, LaTeX est très compliqué. Mais pour simplement mettre des formules dans le Forum, c'est très simple. On apprend par l'exemple.

Cordialement,
Tony

[erik]

Je ne connais pas Latex. Tu pourrais m'expliquer par mp?
Merci.

Tu as quelques explications (suffisantes pour l'utilisation sur le forum) ici : http://forums.futura-sciences.com/thread12735.html

[leg]

T Rex, bonjour:
la démonstration que vous demandez conserant :
Prouver que Mq = 2^q -1 = (8x)² - (3qy)²
(Alors, Mq est premier s'il y a un seul couple (x,y) solution de [1]).
est démontré par vous si je ne m'abuse!

et c'est en regardant votre relation avec les carrés que cela m'a donné l'idée de recherché une relation dans les carrés (triplets pythagoriciens (8x)² - (3qy)²= X )

mais n'étant qu'un amateur passioné, je n'utilise pas votre langage veuillez m'en excuser.
chaque nombre de mersenne a une relation avec le précedent.
ce qui veut dire que si je prend 2^23 -1 j'ai une relation par les carrés avec 2^29-1

((2^23) -2)* 2 = U² -V², donc comme V = 2,
U² = 2² + (2^23 * 2) par conséquent, U = √U².
Exemple : 8388606 * 2 = 16777212, et + 4 = U², soit √16777216 = U = 4096 et bien sûr, 4096 / 2 = 2048 ce qui donne :
v’ = 2048 – 1 ; et u’ = 2048 + 1, qui sont divisibles par 23 et 3,

2047 / 23 = 89 ; 2049 / 3 = 683

et bien sûr: u' * v' = 2049*2047 = (2^23 -2) /2.

pour constituer les deux carrés a² et b² on utilise u' et v' mais en gardant 3 de côté ce qui donnera : pour a :
(2047 = 23*89); (2047 + 683 ) /2 = 1365 = a
pour b : a - 683 = 682 .

pour 2^29-1, = (U² - 4)/2; soit ((32768² - 4) /2) +1

on va utiliser U, u' et a de2^23-1
cela nous donne:

U * 8 = 32768; (u'-1) * 8 = 16384 , et + 1= 16385 et 16384 - 1 = v'
u' = 16385.
v' = u' -2 = 16383
qu' en est - il, de: a et b ?

les facteurs P (3,23,89,et 683); divisant (2^23 -2)/2 ; ne peuvent pas être les mêmes, que ceux de (2^29 -2)/2
16385/5/29 = 113 ;
16383 /3 = 5461 qui restera a factoriser. = 43 et 127.

a = 1365 * 8 = 10920 et 10920+3 = 10923
b = 682*8 = 5456 et 5456 + 6 = 5462.

ce qui correspond bien à: (16385 + 5461)/2 = 10923 = a
a - 5461 = 5462 = b

encore deux précision; U/a = 3 quelque soit Mq -1

A /U = 21,7 et A/a = 65,4 pour Mq -1, q=23
A/U = 35,16 et A / a = 105,9

racine carré de u'/2 nous donne le milieu entre le facteur P a trouver et A/U

Donc si Mq est composé, il existe deux carrés A² - B² = Mq - 1

pour Mq - 1 = 2^23-1 ; A = 89264 et B = 89217 ; A - B = 47

pour Mq -1 = 2^29-1; A=1152200 et B =1151967; A - b = 233

Alors voilà ce que j'ai supposé:

1) on factorise de façon très simple [2^(p-1) -1] /2 !

2) on trouve a et b et on sait qu'il y a un indice multiplicateur pour remonter Sur A ET B quelque soit cet indice,il nous donne déjà l'information, de la valeur du facteur P divisant Mq; car ce facteur P n'est autre que la différence entre A et B;
donc le plus petit facteur P divisant Mq-1 si il est composé.

3) en se servant des carrés de Mn -1 toujours dans cet exemple A = 89264 *8 = A <A de 2^29-1 au minimum, car A pour 2^29-1 = 1152200 !

4)les différences entre A/u et A/a vont nous donner une indication car 89264*8 = 714112
On suppose A < à A réel pour 2^29-1,
714112/ 10923 = 65 ce qui veut dire que cet indice n’est pas très éloigné de l’indice réel et en multipliant au minimum par 2, on obtient 130 et 130*10923 = 1419990 il ne reste qu’ à mettre A et B au Carré pour voir ou on se trouve par rapport au facteur recherché. B = 1419800 ; A – B = 190 le facteur P, étant 233
De plus 1419990 / 89264 = 15.9 donc on peut supposer que A recherché est < a 1419990 donc P est > 191

5) en conclusion comme l’écart entre les facteur P grandira du fait de l’exposant P, on retrouvera cet écart avec les carrés du dernier nombre de Mersenne U, u’, et a , les indices et A.

de plus si le dernier facteur P est petit, au lieu de multiplier A par 8 il faut diviser ex entre Mq exposant 37 et 41 , les facteurs sont 223 et 13367 donc A pour ce facteur P est < a A pour le facteur 223 , ce qui donne 308159200 = A / 8 =38519900
Le A recherché = 82262360 mais comme U/U = 4 on peut commencer avec A/4 ce qui donne 38519900*2= 77039800 beaucoup plus proche de la réalité.

voila monsieur T reix ce que j'ai trouvé.
je suppose que 3 dans votre carré (3qy)² est en rapport avec ceci ainsi que pour 8.
mais attention si je prend 2^37 et 2^41 alors j'utilise 4 et non 8
exemple: U = 524288; U * 4 = 2097152 pour 2^41 -1.

ma conclusion serait qu'il y a, à travers ces relations, entre chaque nombre de Mersenne Mn, une formule pouvant touver directement ce petit facteur P divisant Mn composé, sans trop d'opération.

[leg]

bonjour,
sph,
ces nombres ne divisent que 2^(p-1)-1 avec p premier , donc il ne seront jamais des diviseurs de
2^p-1 (avec p premier) lorsqu'ils sont composés ;
exemple 19 divise 2^18-1 donc il divisera tous les 2^18a-1 idem pour les autres )
voila
bon courage jeune homme

bonjour tigli
tous les nombres premiers divisent au moins une fois ((2^(p -1)-1)/2 ta remarque est donc injustifiée prend exemple avec 23 il divise 2^11-1 et il divise (2^22) -1 ou encore:
2^127-1 est premier. pourtant 127 divise 2^(29-1)-1 etc etc ..
il doit être possible effectivement, de montrer que 75 % des exposants P donnent un mersenne composé!

[leg]

concernant la relation (8x)² -(3qy)² = Mq -1 premier, cela implique que le couple x et y ne sont pas des entiers.
il apparait aussi que si (3qy)²+ Mq-1 = 4(9),avec y impair et entier, alors Mq-1 serait composé, ce qui ne serait pas toujours le cas si (3qy)² + Mq -1 = 1 ou 7 (9) toujours en prenant y entier est impair.

[invitecf787e7b]

Bonjour,
Il faut toujours se mefier des evidences...
Il es clair qu'il fallait considerer que :
SI p est premier, p divise 2^(p-1)-1 (petit th de fermat )
donc p ne divise pas les 2^q -1 , avec q premier et SUPERIEUR a p (c'est cela qui etait sous entendu )
voila

[invitecf787e7b]

bonjour tony,
j'ai fait votre petit exercice ..j'ai fini par trouver une preuve courte ; il suffit de considerer :
Mp=2^p-1=ab et de poser ensuite U=(a+b)/2 et V=(a-b)/2 ce qui donne Mp=U²-V²
ensuite il faut prouver que 8 | U ; 3 | V ; p | V ;ce qui se fait aisement .
je le proposerai à mes eleves....
merci encore

[leg]

bonsoir tigli, cela implique que b = 1 pour chaque couple a*b.
ce qui nous ramène dans les triplets Pythagoriciens, chaque triplet primitif étant unique, le couple a b étant aussi unique, et premier entre eux .
pour X impair = U² - V² et bien sûr U+V = a; et U - V = B = 1
U = 16; V = 15
Y = 2UV
Z = U² + V²
et puisqu'on y est; (2^p -1)² = (Z+y) (Z-y) = 961.

[invitecf787e7b]

leg,
en consultant la liste de nombres premiers de sph, vous pourrez constater que ces nombres n'apparaissent pour la PREMIERE FOIS ,comme diviseurs dans la suite des Mersenne que, pour p donné , la valeur 2^(p-1)-1
c'est a dire 3 | 2²-1 ; 5 | 2^4-1 ; 11 | 2^10 -1 ; 13 | 2^12-1 etc
ce qui n'est pas le cas de vos contre-exemples 23 | 2^22-1 et divise 2^11-1 donc ce n'est pas la premiere fois qu'il apparait puisqu'il divise 2^((p-1)/2) -1( idem pour 127 )
voila

[leg]

c'est exact tigli.
mais les diviseurs de 2^(p-1) -1 ne donnent aucune indication pour savoir si 2^q - 1 est composé
c'est pour cela que je garde 3 dans les remarques que je fais plus haut, 3 divise tous les 2^(p-1) -1 donc dans la construction des carrés je ne m'en sert pas.
de plus cela donne une explication dans ce qu'a montré tony.(3qy)² .
donc on en déduit que y = les facteurs p différent de 3 et q et parfois 5.
tout comme x est une puissance de 2.
mais la question reste entière comment savoir et montrer, que le couple X,Y est unique
car dans le cas de 2^11 -1 , Y = 31
U = 2^10= 1024
V = U -1 = 1023
8 divise U , =128 ; et 128/2 = 8² = X
3 divise V = 341; et 341/11 = 31 =Y
Y est par conséquent unique
mais il existe un autre couple A et B tel que A² - B² = 2^q -1 et dont le premier fa

[SPH]

3 divise tous les 2^(p-1) -1

Si tu parles de la racine primitive modulo p, elle n'est helas pas presente partout. Si c'etait le cas, ce serait le bonheur total pour moi.
Liste plus complete