Equazione diofantea

[Montecristoh]

Ciao,

ultima tipologia di esercizio per oggi che voglio fare
Devo calcolare tutte le soluzioni intere della seguente equazione diofantea: $32x+103y=2$

Sto seguendo la procedura descritta qui: http://it.wikipedia.org/wiki/Equazione_ ... ea_lineare

Considero l'equazione come se fosse nella forma $32x+103y=1$
Eseguo l'algoritmo di Euclide.
$103=32*3+7$
$32=7*4+4$
$7=4*1+3$
$4=3*1+1$
$3=1*3+0$
Ora riscrivo mettendo in evidenza i resti
$7=103-32*3$
$4=32-7*4$
$3=7-4*1$
$1=4-3*1$
$0=3-3*1$
Ora... devo partire a ritroso e sostituire i valori
$0=3-3$
...e qui ho il problema, a questo punto non mi torna la procedura, avrei dovuto sostituire 3 con il resto del risultato precedente... ma non posso perchè sono valori diversi, ho sbagliato qualcosa nell'algoritmo di Euclide?

[Lorin1]

Io di solito quando riscrivevo mettendo in evidenza partivo dal basso, ovvero usando il teorema di Bezout scrivevo $1=4-3*1$ e proseguivo a ritroso, sostituendo man mano che salivo i valori che ricavavo, fino a trovare una cosa del tipo $1= ax+by$ dove (x,y) era la soluzione dell'equazione.

[Montecristoh]

"Lorin":Io di solito quando riscrivevo mettendo in evidenza partivo dal basso, ovvero usando il teorema di Bezout scrivevo $1=4-3*1$ e proseguivo a ritroso, sostituendo man mano che salivo i valori che ricavavo, fino a trovare una cosa del tipo $1= ax+by$ dove (x,y) era la soluzione dell'equazione.

Mh... quindi non dovrei partire dallo 0.

[Paolo902]

"Montecristoh":

Mh... quindi non dovrei partire dallo 0.

Esatto. Si riparte sempre dall'ultimo resto non nullo che, per inciso, nell'algoritmo di Euclide è proprio il GCD.

[Montecristoh]

Ok... l'ho finita, ecco cosa mi risulta

$1 = 4-3 = 4-(7-4) = 4-7+4 = 2*4-7 = 2(32-7*4)-7 = 2*32-8*7-7 = 2*32-9*7 = 2*32-9(103-32*3) = 2*32-103*9-27*32 = -25*32-103*9$

Il problema è che sostituendo mi viene $32*(-25)+103(-9)=1$ che non è per nulla una identità, quindi ho sbagliato qualcosa, ma non capisco cosa... mah. Suggerimenti?

[Paolo902]

Errore di segno, capita, nulla di grave. Qui:

"Montecristoh":
$ = 2*32-103*9-27*32 $= -25*32-103*9$

Il termine in grassetto è positivo. Viene infatti $32*(29)+103(-9)=1$, che è vera. Moltiplichi per due ambo i membri e hai finito.

[Montecristoh]

Grazie.

[Paolo902]

Prego!