Petit devoir maison

[NoctisX55]

Bonjour,
je souhaiterais obtenir l'aide de quelqu'un afin de m'aider à faire mon DM de math spé. Je tiens à préciser que je n'ai répondu à aucunes questions, puisque je n'arrive pas à mettre en place le tableur --'. Et pour cause, le tableur m'indique que la capacité (mémoire) de mon ordinateur est insuffisante  .
Je remercie d'avance ceux ou celles qui m'aideront!

Énoncé:

Pour les nombres de Mersenne, il existe une méthode beaucoup plus efficace qu'un test de primalité classique. Cette méthode, appelée test de Lucas-Lehmer, s'appuie sur le  principe suivant:

Étant donné un nombre premier p, on souhaite déterminer si le nombre de Mersenne M_p est premier ou non.
On considère alors la suite (Un) d'entiers tels que U₀=4 et, pour tout entier naturel n,
U_n+1 est le reste de la division euclidienne de U_n²-2 par M_p.
On sait alors [résultat admis] que M_p est premier si, et seulement si, le terme U_p-2 est nul.

On se propose de tester l'efficacité de cette méthode.

a) Appliquer la méthode pour tester la primalité du nombre M13. On utilisera un tableur pour ceci (aide: la formule = MOD( ; ) permet d'obtenir un reste).

b) Combien d'étapes de calcul ont-elles été nécessaires pour obtenir le résultat précédent?

c) Avec le même procédé, tester la primalité de M₁₇, M₁₉ et M₂₃. Sur tableur, on peut utiliser la même feuille de calcul pour tous les tests.

d) Combien d'étapes de calcul sont-elles nécessaires pour tester M₂₉

Sur ce je vous souhaite une bonne journée!

[Barbidoux]

a)---------------

[Denis CAMUS]

Grillé par Barbidoux !

 

test.xlsx

[NoctisX55]

Bonjour,

tout d'abord je tiens à vous remercier de votre immense aide! Néanmoins serait-il possible, s'il vous plaît, que vous me fassiez une nouvelle capture d'écran pour pour M13, M17, M19 et M23 ? Je sais que je demande beaucoup mais mon ordinateur n'est pas assez puissant ^^'.

 

Sur ce je vous souhaite une bonne journée!

P.S: Je posterai mes réponses à 13h, là je dois préparer mon repas ^^'.

[Denis CAMUS]

Tu as combien de mémoire pour être aussi limité ?

Tu ne peux même pas ouvrir le tableau que j'ai mis ?

 

 

[NoctisX55]

Bonjour,

une nouvelle fois je vous remercie de votre aide. Pour répondre à votre question, j'ai 30Mo de mémoire puisque j'ai, dans Windows C:, un fichier de plus de 700Go (je ne sais pas si c'est dangereux ou non de le supprimer ^^'). Sinon je souhaiterai vous demander une nouvelle fois de l'aide s'il vous plaît. Notre prof., nous a donné une liste des 100 premiers nombres premiers et 23 et 29 n'y figurent pas. Comment on peut déterminer le nombre de calcul nécessaire pour tester M29 et M23, alors qu'ils ne sont pas premier ?

[Denis CAMUS]

C'est pas très clair. 23 et 29 sont bien des nombres premiers. Tu veux sans doute dire que M23 et M29 ne sont pas premiers.

il y a 35 minutes, NoctisX55 a dit :

Notre prof., nous a donné une liste des 100 premiers nombres premiers et 23 et 29 n'y figurent pas. Comment on peut déterminer le nombre de calculs nécessaires pour tester M29 et M23, alors qu'ils ne sont pas premiers ?

Citation

On sait alors [résultat admis] que M_p est premier si, et seulement si, le terme U_p-2 est nul.

Tu regardes dans le tableau si la ligne n=p-2 est nulle. Autrement dit, dans la colonne de M23 ou M29, est-ce qu'il y a un 0 pour n = 21 ou n = 27 ?

Malheureusement, les tableurs ne calculent qu'avec 15 chiffres significatifs, ce qui fait que l'on est un peu coincé pour M29, mais rien ne t'empêche de faire les calculs à la main, ou avec la calculette de Windows qui travaille sur plus de 15 chiffres.

[NoctisX55]

Bonjour,

encore et toujours je vous remercie de votre aide! Sinon je vous prie de m'excuser de mon ancien message, je m'étais mal exprimé. Notre prof., nous a donné la liste des 100 premiers nombres de Mersenne premier. Sinon j'ai supprimé le fichier de 700Go et j'ai fait ce que vous m'avez dit. Cependant pour M29, Up-2 n'est pas nul, donc il a fallu 27 calculs afin de tester M29.

[Denis CAMUS]

Tu arrives à calculer M29 avec Excel ?

[Barbidoux]

On sait alors [résultat admis] que Mp est premier si, et seulement si, le terme Up-2 est nul. Le nombre de calcul nécessaire au test est donc de p-2. Le problème réside dans calcul de l'entier Mp ce qui est possible (avec Excel) jusqu'à p≤37

[Denis CAMUS]

" Tu arrives à calculer M29 avec Excel ? "

Je me suis mal exprimé. J'ai voulu dire :

Arrives-tu à faire le test avec M29.

 

Sinon pas de problème pour calculer Mp, mais c'est après avec le carré que ça déborde, lors du calcul de mod(U_n²-2; M_p) . A moins que je me sois fourré le doigt dans l'oeil avec mon tableau de 10h22.

Arrives-tu à tester M29 ?

[NoctisX55]

Bonsoir,

oui, je pense avoir réussi le test de M29 grâce à votre tableur. Pour U27, soit Up-2, j'ai 227858577. Et j'obtiens le même résultat en faisant le calcul à la main, sauf erreur de ma part ^^'.

[Denis CAMUS]

Je ne vois pas comment tu as pu faire le test de la primalité de M29, car à partir de n=5, la fonction MOD perd les pédales et on a l'erreur #NOMBRE!.

J'ai essayé de la contourner en utilisant =((F5^2-2)/F$2-QUOTIENT(F5^2-2;F$2))*F$2, mais je me suis aperçu que malgré des résultats dans toutes les lignes, c'était faux par rapport à la calculette de Windows qui calcule sur 32 chiffres.

Finalement, le tableur de xcas donne les bons résultats, du moins par rapport à la calculette :