Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. PremièreForum de première ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau première
Partager :

Algorithme d'Euclide

Posté par
Nijiro 26-04-20 à 17:41

Bonjour,
1. En utilisant l'algorithme d'Euclide, déterminer:
(212-1)(28-1) et  (214-1)(210-1) (déjà fait)

2. Soit m et n deux entiers tels que: 0<mn.
a) Soit r le reste de la division euclidienne de n par m.
     Montrer que 2r-1 est le reste de la division euclidenne de 2n-1 par 2m-1.

=>n=qm+r; \; q\in Z \; et\; 0\leq r<|m|
2^n-1=2^{qm+r}-1=2^{qm}\times 2^r-1=(2^{qm}-1+1)\times 2^r-1=((2^m-1)\sum_{i=0}^{q-1}{2^{im}}+1)\times 2^r-1= 2^r(2^m-1)\sum_{i=0}^{q-1}{2^{im}}+(2^r-1) d'où le résultat.

b) on pose: D=(2n-1)(2m1) et d=mn.
En utilisant l'alogrithme d'Euclide, exprimer D en fonction de d.
c) En déduire que:
(2^n-1)\wedge (2^m-1)=1\Leftrightarrow m\wedge n=1

Merci d'avance.

Posté par
flightre : Algorithme d'Euclide 26-04-20 à 18:05

salut

avec les congruences pour la question a)

2m-1 = 0[2m-1]
2m = 1[2m-1]
(2m)^q = 1[2m-1]
(2mq) = 1[2m-1]
(2mq)* 2r =2r[2m-1]
(2mq+r)=2r[2m-1]
et  (2mq+r)-1=2r-1[2m-1]
et voila   ( sinon c'est vraiment un sujet de première?)

Posté par
flightre : Algorithme d'Euclide 26-04-20 à 18:06

pour fignoler la fin : 2n-1 = 2r-1[2m-1]

Posté par
Nijirore : Algorithme d'Euclide 26-04-20 à 18:07

flight @ 26-04-2020 à 18:05

( sinon c'est vraiment un sujet de première?)

Je ne comprends pas??

Posté par
Nijirore : Algorithme d'Euclide 26-04-20 à 18:08

flight @ 26-04-2020 à 18:06

pour fignoler la fin : 2n-1 = 2r-1[2m-1]

ça marche et a l'air plus facile.
Mais ma proposition est-elle correcte?

Posté par
carpediemre : Algorithme d'Euclide 26-04-20 à 18:19

salut

oui c'est tout à fait satisfaisant ... j'aurai simplement sorti le +1 plus rapidement ...

Posté par
Nijirore : Algorithme d'Euclide 26-04-20 à 21:32

D'accord Carpediem
Pour 2.b : Rien n'est si claire pour moi. Bon, selon l'algorithme d'Euclide, (2^n-1)\wedge (2^m-1)=(2^m-1)\wedge (2^r-1), quoi encore, pas d'idées! Bon je pense à: n\wedge m=m\wedge r Toutefois, que d'ambiguïté

Posté par
carpediemre : Algorithme d'Euclide 27-04-20 à 09:07

il suffit d'écrire m = dp et n = dq avec p^q = 1 puis tu écris 2^m - 1 et 2^n - 1 comme tu l'as fait en 1/ ...

Posté par
Nijirore : Algorithme d'Euclide 27-04-20 à 17:03

voilà à ce que j'ai pensé:
pour 2.b: comme vous avez dit:
Comme n\wedge m=d alors: n=dp et m=dq avec p\wedge q=1, donc:
2^n-1=2^{dp}-1=(2^d-1)\sum_{i=0}^{p-1}{2^{id}} et 2^m-1=2^{dq}-1=(2^d-1)\sum_{i=0}^{q-1}{2^{id}}.
On a donc:
D=(2^n-1)\wedge (2^m-1)=(2^d-1)\sum_{i=0}^{p-1}{2^{id}}\wedge (2^d-1)\sum_{i=0}^{q-1}{2^id}=(2^d-1)(\sum_{i=0}^{p-1}{2^{id}}\wedge \sum_{i=0}^{q-1}{2^{id}})=(2^d-1)((2^p-1)\wedge (2^q-1))

Posté par
Nijirore : Algorithme d'Euclide 27-04-20 à 17:05

Nijiro @ 27-04-2020 à 17:03

D=(2^n-1)\wedge (2^m-1)=(2^d-1)\sum_{i=0}^{p-1}{2^{id}}\wedge (2^d-1)\sum_{i=0}^{q-1}{2^id}=(2^d-1)(\sum_{i=0}^{p-1}{2^{id}}\wedge \sum_{i=0}^{q-1}{2^{id}})=(2^d-1)((2^p-1)\wedge (2^q-1))


Je corrige une petite erreur:
D=(2^n-1)\wedge (2^m-1)=(2^d-1)\sum_{i=0}^{p-1}{2^{id}}\wedge (2^d-1)\sum_{i=0}^{q-1}{2^{id}}=(2^d-1)(\sum_{i=0}^{p-1}{2^{id}}\wedge \sum_{i=0}^{q-1}{2^{id}})=(2^d-1)((2^p-1)\wedge (2^q-1))

Posté par
Nijirore : Algorithme d'Euclide 27-04-20 à 17:14

Nijiro @ 27-04-2020 à 17:05


D=(2^n-1)\wedge (2^m-1)=(2^d-1)\sum_{i=0}^{p-1}{2^{id}}\wedge (2^d-1)\sum_{i=0}^{q-1}{2^{id}}=(2^d-1)(\sum_{i=0}^{p-1}{2^{id}}\wedge \sum_{i=0}^{q-1}{2^{id}})=(2^d-1)((2^p-1)\wedge (2^q-1))


Une autre erreur:
D=(2^d-1)((2^p-1)\wedge (2^q-1)) si d=1, c'est pour 2.c, mais pour la question 2.b, on s'arrête à: D=(2^d-1)(\sum_{i=0}^{p-1}{2^{id}}\wedge \sum_{i=0}^{q-1}{2^{id}})

Posté par
carpediemre : Algorithme d'Euclide 27-04-20 à 17:59

ouais ... peut-être n'est ce pas une bonne idée ...

enfin faut voir ...

on peut toujours supposer m = pd  < n= qd donc p < q

alors \sum_0^{q - 1} 2^{kd} = \sum_0^{p - 1} 2^{kd} + \sum_p^{q - 1} 2^{kd} = \sum_0^{p - 1} 2^{kd} + 2^p \sum_0^{q - 1 - p} 2^{kd}

en posant s(p) = \sum_0^{p - 1} 2^{kd} alors :

s(p) est impaire et donc pgcd [s(p), s(q)] = pgcd [s(q), s(q - p)] = ... = 1 (car p et q sont premiers entre eux) (enfin montrer plus clairement ...

sinon suivre l'indication et faire l'algo d'Euclide dès le départ ...

Posté par
Sylvieg Moderateurre : Algorithme d'Euclide 29-04-20 à 07:32

Bonjour,
Il me semble que les sont inutiles.
D'après 2)a), le reste est nul dans la division de n par m si et seulement si le reste est nul dans la division de 2n-1 par 2m-1.

Exemple d'utilisation de 2)a) avec 214-1 et 210-1 :
14 = 10 +4 ; donc pgcd(214-1, 210-1) = pgcd(210-1, 24-1). En effet, d'après 2)a), 24-1 est le reste de la division de 214-1 par 210-1.

10 = 42 +2 ; donc pgcd(210-1, 24-1) = pgcd(24-1, 22-1) . De même.

4 = 22 ; donc 20-1 est le reste de la division de 24-1 par 22-1. Et 22-1 est le dernier reste non nul de l'algorithme d'Euclide pour 214-1 et 210-1.

A mettre en forme dans le cas général.

Posté par
Nijirore : Algorithme d'Euclide 07-05-20 à 18:44

Je ne sais pas comment exprimer D en fonction de d en utilisant l'algorithme d'Euclide, car je ne sais pas le dernier reste non nul.
Juste: (2^m-1)\wedge (2^n-1)=(2^m-1)\wedge (2^r-1), et donc on remplace m par dq et ça donne:
D=(2^{dq}-1)\wedge (2^r-1)

Posté par
Sylvieg Moderateurre : Algorithme d'Euclide 08-05-20 à 08:21

Bonjour,
Je ne suis plus vraiment "dans le bain" et j'ai jeté mes notes sur le sujet.

2 pistes :
1) Pour conjecturer l'expression de D en fonction de d, regarder les résultats de 1).
pgcd(12, 8) = 4 et pgcd(212-1, 28-1) = 15
pgcd(14, 12) = 2 et pgcd(214-1, 212-1) = 3

2) Remplacer "nul" par "non nul" dans

Citation :
le reste est nul dans la division de n par m si et seulement si le reste est nul dans la division de 2n-1 par 2m-1.
Et compléter
Citation :
Et 22-1 est le dernier reste non nul de l'algorithme d'Euclide pour 214-1 et 210-1.
alors que 2 est le dernier reste non nul de ...


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !