Inscription / Connexion Nouveau Sujet
Remonter l'algorithme d'Euclide - Equation du type au+bv=1
Bonjour,
Je viens de me rendre compte que j'ai vraiment des difficultés pour remonter l'algorithme d'Euclide, je m'y prend mal, je ne sais pas quand il faut simplifier, mettre en facteur, sans parler des erreurs de signe... Bref je m'emmêle les pinceaux.
Par exemple, soit (E) : 23x -26y = 1.
Je commence par calculer leur PGCD avec l'algorithme d'Euclide et j'en profite pour vérifier qu'ils sont bien premiers entre eux (pour utiliser si besoin Gauss).
On a 26 = 23x1 +3
23 = 3x7 +2
3 = 2x1 +1
2 = 1x2 +0.
Donc PGCD(23;26) = 1.
Malgré tout, maintenant j'essaie de trouver x et y mais je n'y arrive pas...
1 = 3 - 2x1
1 = (26 -23x1) - (23-3x7x1)
Et après je suis perdu... Que ce soit pour cet exemple simple ou pour d'autre vraiment beaucoup plus compliqués.
Aidez moi s'il vous plait 
D'accord merci beaucoup, donc une seule chose à la fois.
Vous auriez d'autres exemple pour voir si j'ai saisi s'il vous plait?
Oh, prends au hasard! Des nombres premiers entre eux courent les rues... Et quand tu crois avoir fini, tu fais le dernier calcul pour vérifier que tu as bien trouvé 1. Tu peux même vérifier que tu as 1 à chaque étape, ça évite les fautes de calcul.
Par exemple 16x -9y = 1.
16 = 9x1 + 7
9 = 7x1 + 2
7 = 2x3 +1
2 = 1x2 +0
PGCD(16;9)=1.
1 = 7- 2x3
1 = 7 - (9-7)x3
1 = 7 x 4 - 9x3
1 = (16-9)x4 -9x3
1 = 16x4 -9x7
Donc le couple (4;7) est solution ^^
Bonsoir,
Quand j'enseignais l'arithmétique, je conseillais à certains élèves qui se perdaient dans les " chiffres " d'utiliser des expressions littérales sauf pour les quotients obtenus :
Je reprends l'exemple :
16 = 9x1 + 7
9 = 7x1 + 2
7 = 2x3 +1
En utilisant des expressions littérales sauf pour les quotients obtenus.
L1 : a = b * 1 + r1 soit a = b + r1
L2 : b = r1 * 1 + r2 soit b = r1 + r2
L3 : r1 = r2 * 3 + r3 soit r1 = 3 r2 + r3
On exprime tous les restes obtenus
L1 : r1 = a - b
L2 : r2 = b - r1
L3 : r3 = r1 - 3 r2
D'après L3 : r3 = r1 - 3 r2
D'après L2 : r3 = r1 - 3 ( b - r1 ) = 4 r1 - 3 b
D'après L1 : r3 = 4 ( a - b ) - 3 b = 4 a - 7 b
On a r3 = 4 a - 7 b soit 1 = 4 * 16 - 7 * 9 .
Cordialement.
Ah oui c'est intéressant de voir la chose sous cet angle!
J'essaierai de m'en souvenir si je bloque, merci 
Tu en fais un ou plusieurs toi-même jusqu'à ce que la méthode soit assimilée.
L'idée est assez simple.
On garde le dernier reste non nul.
En remontant l'algorithme d'Euclide , on remplace tous les restes au fur et à mesure jusqu'à ce qu'on obtienne une relation entre le dernier reste non nul et les deux nombres a et b de départ.
En général au bout de deux ou trois exemples , on retient la méthode presque " ad vitam eternam " .
Je ne l'avais pas refait depuis 7 ou 8 ans et cela m'est revenu tout de suite car je me souvenais qu'il fallait uniquement garder les valeurs numériques des quotients.
Bon courage pour la suite.
Annuler
connectez vous