je repasse une matière (bouh) de Math expérimentale avec des ordinateurs et compagnie.
Je fais les annales, et j’avoue que je galère.
Donc je demande de l’aide ici, espérant que vous pourrez m’aider (exam demain … :)")
Donc voilà, on demande de prouver que k^25 - 1 est composé pour tout k >= 2
question 2 : est-ce vrai aussi pour k^5 - 1 ?
Sachant que dans un autre sujet, on demandait de montrer que si n est composé, alors 2^n - 1 l’est aussi (nombres de mersenne).
Ça grâce à wikipedia et aux séries géométriques, il semble qu’on puisse se débrouiller pour prouver que c’est vrai, mais pour le cas du dessus, je vois pas.
Question, a tout hasard : composé, ça veut bien dire “non premier” ?
Si oui, je cherche encore pour le reste mais pour k^5-1, c’est tout simple je pense : il suffit de trouver un contre exemple, non ?
Et ce contre exemple tu l’as avec k =2, qui donne 31 et qui est bel et bien premier.
Enfin, tout ça n’est juste que si je ne me goure pas…
Bah pas si l’exposant est impair (enfin, que je sache), car on a a^k - b^k = (a^(k/2) - b^(k/2))(a^(k/2) + b^(k/2)).
Maintenant, avec j = (k^5), on a j^5 - 1. Mais on a prouve que c’etait pas bon, et comme le 1 dit qu’on doit prouver que c’est bon, c’est pas aussi simple.
Je pense pas… k^25 ne peut pas se décomposer en puissance de deux donc bon.
Sinon, déjà, tu peux déterminer que k^25-1 est composé pour tout k>=2 ET impair. Ben oui, si k est impair, k^25 aussi et donc k^25-1 est pair, donc composé.
Après, ça te permet de travailler sur (2x)^25-1 avec x impair mais je sais pas si ça aide.
Putain, que mes cours de maths me semble loin…
Comme ça à vu de nez, je le démontrerais par induction (ou récursion aussi).
tu fais l’ancrage (tu montres que c’est vrai avec k=2)
ensuite en supposant que c’est vrai pour k = n (quelconque) tu dois montrer que c’est vrai pour k = n+1 … mais bon, le seul truc c’est que (n+1)^25, on va pas le développer hein, ça serait un peu lourd …
Donc du coup plus si sûr que ça soit la méthode absolue, mais bon, peut-être que ça peut t’aider
[quote=“Longfield, post:6, topic: 47655”]Comme ça à vu de nez, je le démontrerais par induction (ou récursion aussi).
tu fais l’ancrage (tu montres que c’est vrai avec k=2)
ensuite en supposant que c’est vrai pour k = n (quelconque) tu dois montrer que c’est vrai pour k = n+1 … mais bon, le seul truc c’est que (n+1)^25, on va pas le développer hein, ça serait un peu lourd …
Donc du coup plus si sûr que ça soit la méthode absolue, mais bon, peut-être que ça peut t’aider[/quote]
J’ai trouve un truc dans Wikipedia:
x^n - 1 = (x - 1)(x^n-1 + x^n-2 + … + x + 1)
Voila, maintenant tu montres comment tu factorises a gauche pour le truc a droite, et HOP, tu as prouve la premiere question, MAIS pour n > 2, donc faut dire que 2^n - 1 marche avec Mersenne.
Ce qui fait que 1), c’est bon (25 est compose), mais 2) pas bon (pas compose, donc on peut avoir le cas ci-dessus avec 2^5-1).
Merci à tous pour votre aide.
La réccurence je voyais pas trop l’hérédité, par contre pour la dernière solution jsuis un peu deg de pas avoir trouvé ça lors de mes recherches …
Je débroussaille et reposte d’autres coles ou des détails si besoin.
Grmpf j’ai vraiment du mal avec la somme des puissances comme ça.
J’avais cherché une décomposition de la puissance de 25 mais je tombais pas du tout sur ce genre de trucs
et pour k^5-1, k^5-1 = (k-1) (k^4 + k^3 +k^2+k+1)
donc les nombres k^n-1 sont composés (sauf pour n = 2, car le premier terme serait égal à 1).
Et une démo plus simple serait :
k == 1 mod(k-1)
k^n == 1 mod (k-1)
d’ou k^n-1 == 0 mod(k-1).
(et encore une fois, ca ne marche que parce que k!=2. Sinon, on a un nombre premier avec 1… Ce qui signifie que c’est un nombre :))
[quote=« fser, post:11, topic: 47655 »]Grmpf j’ai vraiment du mal avec la somme des puissances comme ça.
J’avais cherché une décomposition de la puissance de 25 mais je tombais pas du tout sur ce genre de trucs
/me prend un bout de papier et essaye de piger[/quote]
En fait c’est tout bete, seul les premiers et derniers termes restent du developpement, les autres s’annulent :
En fait, d’une maniere general, tu peux abaisser la puissance de k^x - 1 a volonté en factorisant k - 1 (par ex):
k^x - 1 = [k - 1] * [k^(x-1) + k^(x-2) + .... + k^2 + k + 1]
= k^x + k^(x-1) + ... k^2 + k (developpement de k * la parenthese)
- k^(x-1) - ... k^2 - k -1 (developpement de -1 * la parenthese)
Et donc ca marche de la meme maniere en factorisant toute les decompositions de x. La dans l’exemple on a decomposer x en x-1, mais on pourrait faire la meme chose en factorisant un produit de x plus grand.
Dans l’exo, c’est 25 qu’on a decomposer en 20+5 et en factorisant k^5.
Comme toujours en math, ya deux facon de faire, une super compliquée ou tu vas pas ou bout, et une super élégante et super simple quand tu l’as vu …
Tout le truc, c’est de le voir !
Donc Bravo a Xenox et neomattrix qui ont trouvé la clef !
Si moi j’avais vu, j’étais en train d’y réfléchir.
D’ailleurs le prof a finallement répondu (déplacement toussa, d’où la durée) et c’est bien comme cela qu’ils ont fait.
Cben > oui j’ai refait le calcul et en fait cétoucon ™ merci pour les détails qui clarifient les choses.
