Forum de mathématiques - Bibm@th.net

lepetit

Membre

Inscription : 14-12-2005

Messages : 2

aide pour comprendre euclide étendu.

Bonsoir.

Je compte sur votre tolérance pour m'aider et surtout de ne pas rire. Pour certains ça peut sembler évident. Pourtant le 1er exercice je l'ai compris et je l'ai testé en java et j'ai réussi
Sur la page dont le lien que je donne ci-dessous, en ce qui concerne le paragraphe où on explique ceci : il existe des entiers u et v tels que au+bv=d
A chaque ligne on dit on élimine un nombre donné en multipliant par un autre. exemple 255=1x141+114  x(-21)(on élimine les 114).
Est-ce qu'une âme charitable peut m'expliquer plus en détail cette ligne par exemple. Je pense pouvoir comprendre les autres lignes.
Et quand on dit :

On somme tout, on regroupe, et on trouve :
38×141-21×255=3

Comment on fait pour sommer ?

Merci beaucoup.

<<
http://www.bibmath.net/crypto/complemen … uclid.php3

L'algorithme d'Euclide permet aussi de calculer les coefficients de Bezout de a et b (on l'appelle algorithme d'Euclide étendu). Rappelons que si d est le PGCD de a et b, il existe des entiers u et v tels que au+bv=d. L'algorithme d'Euclide permet de calculer ces coefficients u et v. Pour cela, il suffit de remonter les calcules, en exprimant le pgcd d en fonction des autres nombres.
Ex : Pour 255 et 141, on élimine tout ce qui n'est pas ni 255, ni 141, ni 3.

    27=4×6+3
    114=4×27+6   ×(-4) (on élimine les 6).
    141=1×114+27   ×17 (on élimine les 27, il y en a 1 à gauche, et -16 à droite).
    255=1×141+114   ×(-21) (on élimine les 114).

On somme tout, on regroupe, et on trouve :
38×141-21×255=3
>>

Au

Membre

Inscription : 22-10-2005

Messages : 22

Re : aide pour comprendre euclide étendu.

tout sommer cela signifie sommer toutes les équations (coefficientées)

das l'exemple, on a donc :

27-4*114+17*141-21*255=4*6+3-16*27-4*6+17*114+17*27-21*141-21*114

tu simplifies et tu trouves :

38*141-21*255=3

c'est clair ?

lepetit

Membre

Inscription : 14-12-2005

Messages : 2

Re : aide pour comprendre euclide étendu.

Merci infiniment Au, j'ai compris grâce à toi.

Je vais pouvoir avancer.

Cordialement.