Teorema di Bezout - Discreta 2

[Black27]

Ciao a tutti! Mi sto impantanando in questo teorema di Bezout =P
L'enunciato è il seguente:

Siano $ a,b in ZZ $ . Sia d=(a,b) il loro MCD.
Allora $ EE x,y in ZZ $ tali che

ax + by = d

Il mio problema è il modo con cui trovare x e y! Dovrebbero esserci due modi distinti, ma ho solo due esempi (uno per modo) e non riesco a capire secondo qualche procedimento logico vengono trovati...help! Ecco un esempio:

Per prima cosa: Algoritmo di Euclide per a=212, b=187.

212 = 187 * 1 + 25
187 = 25 * 7 + 12
25 = 12 * 2 + 1

Quindi (212,187) = 1

E fin qui ci sono!! XD I problemi vengono ora, ovvero non riesco a capire i seguenti due modi per trovare x,y! Ecco i due procedimenti che non mi sono chiari:

PRIMO MODO:

1 = 25 * 1 + 12 * (-2)
= 25 * 1 + (187 - 25 * 7) * (-2)
= 187 * (-2) + 25 * 15
= (1 - 7 *(-2))
= 187 * (-2) + (212 - 187) * 15
1 = 212 * 15 + 187 * (-17)

(-2,-15)

(questo è tutto ciò di cui dispongo, aiutatemi non riesco a capire )

SECONDO MODO:

212 * 1 + 187 * 0 = 212 -
212 * 0 + 187 * 1 = 187 -
212 * 1 + 187 * (-1) = 25 * 7 -
212 * (-7) + 187 * 6 = 12 * 2 -
212 * (15) + 187 * (-17) = 1

(...e anche questo è tutto per il secondo modo!)

Vi ringrazio già per l'aiuto

[Black27]

Al primo modo nel frattempo ci sono arrivato da solo come farlo! =) Scrivo per completezza come ci sono riuscito, chissà che servirà mai a qualcuno XD

EX) a = 610, b = 22

Applico l'algoritmo di Euclide

610 = 22 * 27 + 16
22 = 16 * 1 + 6
16 = 6 * 2 + 4
6 = 4 * 1 + 2
4 = 2 * 2 + 0

E a zero termina l'algoritmo. Ora bisogna trovare l'ultimo resto diverso da zero (partendo dal basso quindi...0 no, allora 2)
e creare una combinazione lineare di r(i) e r(i+1) che sia equivalente a 2. In soldoni:

2 = 6 + 4 * (-1)

dove 6 è il primo numero della quarta riga, e 4 è il primo numero dopo l'uguale della quarta riga.
Il numero che moltiplica l'ultima cifra (-1 moltiplica 4) ora moltiplica la prima cifra della riga seguente (-1 moltiplica quindi 16).
E avanti così fino alla fine! Continuando quindi:

2 = 16 * (-1) + 6 * (3)
2 = 22 * (3) + 16 * (-4)
2 = 610 * (-4) + 22 * (111)

che è appunto la combinazione lineare che cerchiamo, tale che

ax + by = d

...è stata dura arrivarci da solo al procedimento tramite quell'esercizio mezzo confuso =P

P.S. se qualcuno mi aiutasse col secondo modo ne sarei davvero molto grato!

[Black27]

Nel frattempo ho trovato il metodo risolutivo anche per il secondo. Se qualcuno avesse per caso bisogno basta mandare un mp