Bonsoir,

Quel est le reste dans la division euclidienne de par ?

2^m-n

Oups c'est plutôt 2^n-m-1.

2ⁿ - 1 = 2^n-m+(2^m -1) + 2^n-m -1

Bonjour,

au lieu de + c'est x au deuxième membre de l'égalité
2ⁿ - 1 = 2^n-m+(2m -1) + 2^n-m -1

Oui je l'ai corrigé à 23 : 03

C'est sur la voie (avec pas mal de coquilles !), mais ce n'est pas encore une division euclidienne.

Pourquoi ?

Parce que rien ne dit que le "reste" est plus petit que le diviseur .

Bonjour,
Dommage d'avoir laissé ce sujet inabouti.
Évoquer l'algorithme d'Euclide en s'intéressant aussi au reste de la division euclidienne de n par m est une piste intéressante.
Mais il y a peut-être plus simple.

Oui, il y a une autre méthode par exemple celle-ci

Si d divise n, alors divise ,
parce que si , alors est effectivement un multiple de .
En particulier en appliquant à d = pgcd(n,m), est un diviseur commun de et , donc de leur pgcd.

Réciproquement, si D est le pgcd de et , on a, par définition, mod D et donc mod D pour tous a et b entiers positifs.
Le théorème de Bézout nous permet d'écrire d comme combinaison linéaire de m et n, mais l'un des deux coefficients est négatif. Il faut donc ruser un petit peu, et comprendre qu'il est toujours possible de trouver u et v positifs tels que modulo (et non modulo d).

On aura donc l'existence de k tel que avec u >= 0 et n >=0
puis, modulo D, .

Ensuite, 2 est premier donc premier avec D (sauf si D = 2 mais c'est impossible car 2^n-1 serait pair comme multiple de nombre pair).
Donc le théorème d'Euler dit que mod et donc D divise

Bonjour,
Est-ce plus simple que la démarche suivante :
Soit la division euclidienne de par . Alors la division euclidienne de par est ,
Ainsi, si est le reste de la division de par , alors est le reste de la division de par . Remarquons que est nul si et seulement si est nul.
L'algorithme d'Euclide calcule le pgcd comme le dernier reste non nul dans les divisions successives. Donc si est le pgcd de et , alors est le pgcd de et .