Bonsoir,

J´ai un DM pour lundi en maths et je bloque.

Dans le 1. on me dit de "calculer le PGCD de 17 et 2005 en utilisant la méthode des divisions euclidiennes successives".

Là, rien de trop compliqué:

2005 = 17 X 117 + 16
17 = 16 X 1 + 1
16 = 1 X 16 + 0
donc PGCD (2005 ; 17)=1

C´est après que je bloque, on me dit: "A l´aide des deux premières divisions euclidiennes de la question 1, trouver deux entiers naturels x et y vérifiant: 17x - 2005y = 1 .

J´ai fait quelquechose qui me semble juste mais je pense qu´il y a une méthode qui sera plus apprécié du prof quant à la résolution du problème. Voilà ce que j´ai mis:

Supposons que y=1 :
17x - 2005y = 1
17x - 2005 X 1 = 1
17x - 2005 = 1
17x = 2005 + 1
17x/17 = 2006/17
x = 118

et 17 x 118 - 2005 x 1 = 2006 - 2005 = 1

Donc voilà, si quelqu´un a une meilleur méthode comme précisé avant, je suis partant, et une idée pour rédiger tout ça aussi ^^ .

Merci

Théorème de Bezout !! si a et b premiers, alors il existe u et v tels que au + bv = 1

Non, je rigole.

Euh, le mieux en fait, est de te servir des deux divisions euclidiennes, vraiment.

Par exemple :

2005 = 17*177 + 16 = 17*177 + 16 + 1 - 1 = 17*177 + 17 - 1
donc : 2005 = 17*178 - 1
donc : 17*178 - 2005*1 = 1

Ah oui, en effet, au dessus c´ets marqué équation de Bézout, mais de toute façon je savais pas ce que c´était.
Merci de ton aide, ça va me tracasser pendant que j´essayerai de dormir sinon.

J´ai deux trois questions:

1. Dans la ligne où tu rajoutes "+ 1 - 1", (je suppose que la réponse ets affirmative mais vaut mieux être sûr) on fait la même chose du côté de 2005?

2. Etant habitué au fait que les profs du collège oblige à tout préciser, le 17 qui s´ajoute au facteur 117 pour faire 118, on peut faire comme ça sans préciser d´où sort ce +1 au facteur?

3. Enfin, après avoir repassé 17 x 118 de l´autre côté, pourquoi le -1 devient 1?

Allez, @+

Bah le +1 -1, tu peux l´ajouter à un seul côté, ca équivaut à ajouter 0.

Pour le 17 qui s´ajoute, bah, tu peux rajouter une étape si tu veux :
17*177 + 17 = 17*(177+1) = 17*178

Et ensuite, pour ta dernière question, je vais détailler mon calcul :

2005 = 17*178 - 1
0 = 17*178 - 1 - 2005
17*178 - 2005*1 - 1 = 0
17*178 - 2005*1 = 1

Oki, merci d´avoir donné de ton temps, j´ai bien tout compris. Me reste quelques exercices pour le DM mais je pense que maintenant que j´ai compris ça le reste devrait aller. Je ferais tout de même un signe si j´ai besoin d´aide.

Encore merci.

Bonsoir,

voilà après être revenu des cours j´ai réussi à faire 2 questions et je rebloque sur une question d´abord je poste ce que j´ai fait aux questions 3. et 4.

3. 2005 = 53 X 37 + 44
44 = 9 X 4 + 8
9 = 8 X 1 + 1
8 = 1 x 8 + 0
PGCD (2005 ; 53) = 1

4. Trouver x0 et y0 tel que 44x0 + 9y0 = 1
44 = 9 X 4 + 8
44 + 1 - 1 = 9 X 4 + 8 + 1 - 1
44 = 36 + 9 - 1
44 = 45 - 1
44 = 9 X 5 - 1
44 - 9 X 5 = - 1
44 X (-1) + 9 X 5 = 1

Et voilà la question à laquelle je bloque:
5. En déduire du 4. et de la deuxième division euclidienne du 3. deux entier relatifs x1 et y1 vérifiant: 53x1 + 44y1 = 1

J´ai trouvé quelquechose le problème c´est que 44 se voit remplacer par un autre nombre:
53 = 44 X 1 + 9
53 = (9 X 5 - 1) x 1 + 9
53 = 9 X 5 - 1 + 9
53 + 1 - 1 = 9 X 5 - 1 + 9 + 1 - 1
53 = 45 + 9 - 1
53 = 54 - 1
53 = 9 X 6 - 1
53 - 9 X 6 = - 1
53 x (-1 qui est donc x1) + 9 X 6 = 1

Si quelqu´un pourrait donc m´aider ça sera sympa ^^ . Merci d´avance.

Je fais un dernier up au cas où quelqu´un pourrait m´aider