Salut

J'ai réussi a faire la question 1 mais je vous la donne quand meme pour avoir tout l'énoncé.


1 Calculer en utilisant l'algorithme d'euclide le PGCD (2¹²-1; 2²¹-1)

2 Soit m et n deux entiers tels que 0<m<n et soit r le reste de la division euclidienne de n par m.
a démontrer, par récurrence, que pour tout entier naturelq, 2^qm-1 est divisible par 2^m-1

b en déduire que 2ⁿ-1 2^r-1 [2^m-1], puis que 2^r-1 est le reste de la division euclidienne de 2ⁿ-1 par 2^m-1.

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

En fait je ne sais pas comentfaire pour toute la question 2. Pouvez vous m'aidez?

Bonjour,

ton prof veut un raisonnement par récurrence OK (bien qu'il existe une méthode plus directe)

Récurrence sur q
pour q = 1 c'est évident
supposons que 2^qm - 1 est divisible par 2^m - 1 et montrons alors que 2^{(q + 1)m} - 1 est divisible par 2^m - 1
2^{(q + 1)m} - 1 = 2^m2^qm-1
Il faut maintenant utiliser une petite astuce: ajouter et supprimer un même terme
2^{(q + 1)m} - 1 = 2^m2^qm- 2^m + 2^m- 1 = 2^m(2^qm- 1) + (2^m - 1)
tu as une somme de deux multiples de 2^m - 1, tu as donc un multiple de 2^m - 1.

Pour la 2.b.
Tu poses n = mq + r
Tu transformes alors 2ⁿ - 1
tu dois utiliser la même astuce : ajouter et supprimer un terme qui est 2^r
et tu démontres que 2ⁿ - 1 = 2^r(2^mq - 1) + (2^r - 1) et la congruence fera le reste...

Bon courage

Bonjour,

J'ai exactement la question 1 à faire, je ne comprends pas comment faire.

Doit-on utiliser ce principe ?

2²¹ = 2¹² * 2⁹ ?

Bonjour,

On écrit les divisions euclidiennes (de la forme avec ) successives:

avec

avec



et (le dernier reste non nul).

Merci de la réponse.. très complète