Algoritmo di Euclide

[Marix]

Ciao a tutti,
ho un problema con l'algoritmo di euclide esteso.
Vi faccio un esempio:
- trova mcd (623,413)
per trovarlo non ho nessun problema:
623= 413 X 1 + 210
413= 210 X 1 + 203
210= 203 X 1 + 7
203= 7 X 29 + 0
quindi mcd=7

- determina a,b € Z : a X 623 + b X 413 = 7
e qui arriva il problema, lo svolgimento sarebbe questo:
1 X 623 + 0 X 413 = 623
0 X 623 + 1 X 413 = 413

1 X 623 + (-1) X 413 = 210
(-1) X 623 + 2 X 413 = 203
2 X 623 + (-3) X 413 = 7
quindi a=2 e b= -3

Però non riesco a capire dove vengono presti i numeri 1, -1; -1, 2; 2, -3 che vengono moltiplicati.
Qualcuno sa spiegarmelo?


Grazie in anticipo.

[maurer]

In pratica devi risalire al contrario l'algoritmo di Euclide... Ti spiego meglio: dal penultimo passaggio di ricavi che $7=210-203$, poi da quello prima ti ricavi $203=413-210$ e vai a sostituirlo nella formula appena trovata, quindi scrivi: $7=210-203=210-(413-210)=2*210-413$; iteri il procedimento finché non ti rimangono soltanto i due termini richiesti. In questo caso si tratta di fare ancora un passaggio:
$7=2*210-413=2*(623-413)-413=2*623-3*413$
che sono proprio i coefficienti che cerchi...
Hai capito?

[Marix]

No non ho capito
In che senso seguire l'algoritmo al contrario??

[maurer]

Segui i passaggi che ho scritto io...
Allora tu hai eseguito l'algoritmo ed hai trovato, in ultimo, che $210=203+7$, d'accordo?
Allora da quest'equazione puoi ricavarti 7 in funzione di 210 e 203, basta che porti il 203 dall'altra parte dell'uguale cambiando di segno; quindi ti rimane $7=210-203$.
Nel passaggio immediatamente precedente dell'algoritmo, tu avevi trovato che $413=210+203$, giusto?
Di qui ti ricavi il 203 in funzione di 413 e 210, cioè $203=413-210$; a questo punto vai a sostituire la nuova espressione per 203 nella formula che abbiamo appena scritto, cioè $7=210-203$; sostituendo trovi: $7=210-(413-210)=210-413+210=210*(1+1)-413=2*210-413$.
Andando avanti così, cioè risalendo l'algoritmo al contrario ti trovi i coefficienti cercati. Adesso è più chiaro?

[silvano38]

Per il calcolo dei coefficienti di Eulero propongo il metodo che è rappresentato nella figura allegata.
Sostanzialmente il quadro contiene nella prima parte il procedimento di Euclide.Vi sono poi due altre colonne
( sovratitolate con "x" ed "y)".Le prime due righe di queste colonne aggiuntive sono fisse con i numeri
(1 0) nella prima riga e (0 1 ) nella seconda .Le altre righe di queste colonne si ottengono così:
x) calcolo di x :si moltiplica il quoziente q della riga precedente per la "x" di questa stessa riga
ed al prodotto si somma la "x" della riga immediatemente superiore
y) calcolo di y : si moltiplica il quoziente q della riga precedente per la "y" di questa stessa riga
ed al prodotto si somma la "y" della riga immediatemente superiore
E così fino alla riga in cui il resto è 0.
Fatto ciò, i numeri di Eulero ( presi con segno opportuno) sono gli ultimi due delle colonne x y.
Non so come la cosa si dimostra ( non ho approfondito) .

[manu0103]

si chiama identità di bezout quella ke ti da quei numeri.ti spiego cm ottenerli.fai una tabella di 4 righe e 5 colonne(il numero di colonne può variare).alla prima riga della prima colonna inserisci il primo numero ke hai in questo caso il 623,alla seconda il 413.alle altre colonne della prima riga inserisci i resti delle divisioni ke hai ottenuto per trovare l mcd fino ad arrivare al 7.mentre all ultima colonna a partire dalla seconda colonna inserisci i risultati delle divisoni(nel tuo caso ttt 1).ora riempiamo le colonne centrali.come ha detto silvano38 alle prime 2 colonne i numeri sn fissi e cioè nella seconda riga della prima colonna va l' uno e nella terza riga va lo zero. nella seconda colonna nella seconda riga metti lo zero e nella terza riga l' uno.i numeri delle seconde e terze righe delle altre colonne si calcolano con questa formula.per i numeri nella seconda riga si prendono in considerazione i due numeri precedenti(sempre della stessa riga) ke chiameremo u e u' e il numero nell ultima riga sotto u', cioè un risultato delle divisioni, ke chiameremo r.la formula è u-(u'xr).per i numeri della terza riga la formula è la stessa sl ke devi prendere i 2 numeri precedenti della sua riga( cioè la terza) ke chiameremo v e v' quindi la formula diventa v-(v'xr).rimpendo così ttt le righe fino a quella del 7 otterrai 2 nella seconda riga e -3 nella terza riga.spero di essere stata chiara

[Marix]

Grazie a tutti....ma purtroppo non mi tornano i conti con nessuno dei vostri metodi

[Lord K]

Tenta di nuovo con questo:

$gcd(759,1752)$