exercice spécialité maths TS congruences

[invite46c33e6e]

Soit n et m tel que 0<m<n. Soit r le reste de la division euclidienne de n par m.

1) Montrer que 2^(n)-1 congru à 2^(r)-1 modulo (2^(m)-1)
Puis que 2^(r)-1 est le reste de la division euclidienne de 2^n-1 par 2^(m)-1.

2) En écrivant l'algorithme d'Euclide pour n et m, démontrer que PGCD ( 2^(n)-1, 2^(m)-1) = 2^(PGCD(n,m))-1.



Bon pour l'instant j'ai réussi à démontrer que 2^(n)-1 = 2^(r)-1 +2^(r).( 2^(qm)-1)
avec q le quotient de n par m , mais impossible de sortir ce q sans des calculs interminables... pouvez-vous m'aider ? :s
-----

[invite57a1e779]

Il suffit d'utiliser .

[invite46c33e6e]

oui je suis d'accord, mais je n'arrive pas à trouver un terme de la forme K.(2^(m)-1). Je trouve toujours quelque chose de la forme K.(2^(m)-1) +K'.

[invite46c33e6e]

autrement dit, comment factoriser 2^(qm)-1 par 2^(m)-1 ?

[A voir en vidéo sur Futura]

[invite57a1e779]

Peux-tu trouver un entier tel que ?
Que peux-tu en déduire sur ?

La question porte sur les congruences et le reste de la division euclidienne. A aucun moment on n'a besoin de factoriser quoi que ce soit.

[invite46c33e6e]

merci beaucoup, je me sens un peu bête maintenant XD

[invite46c33e6e]

en fait, la question 2 n'est pas vraiment plus simple ... quelqu'un aurait une piste ?

[invite57a1e779]

Lorsque tu calcules le pgcd de et par l'algorithme d'Euclide, tu divises par , tu obtiens un reste , tu es ramené à calculer le pgcd de et : tu recommences l'opération...

Pour calculer le pgcd de et par l'algorithme d'Euclide, tu divises par , tu obtiens un reste , tu es ramené à calculer le pgcd de et : tu recommences l'opération...

L'algorithme d'Euclide va comporter les mêmes étapes dans les deux cas : les entiers que tu obtiens dans le premier cas sont les exposants qui interviennent dans le second cas.

Reste à l'expliquer proprement... pour conclure que, si le premier calcul se termine sur , le second se terminera sur .