Qualcuno mi spiega come calcolare meccanicamente i due numeri di Bezout, visto che in fondo si tratta di un procedimento meccanico. Sul libro non l'ho capito tanto bene.
In pratica se a e b sono due numeri interi non nulli e d è il loro massimo comune divisore sarà valida questa equazione: ax + by = d dove x e y sono i due numeri di Bezout, ma come si fa per calcolarli? Qual è il procedimento?
(Mi sembra di aver capito che non sono unici)
Grazie in anticipo
Identità di Bezout
faccio un esempio così capisci meglio
a=52
b=37
d=1
$ 52,0,1 $
52 è il nostro a, 0 è il coefficiente di 37 e 1 = coefficiente di 52
$ 37,1,0 $
37=b, 1 coefficiente di 37, e 0 quello di 52
$ 15,-1,1 $
vedo che 37 nel 52 ci sta al max una volta e quindi faccio $ a+[-1(b)] $ la stessa cosa lo faccio anche con i coefficienti
$ 7,3,-2 $
7 nel 15 sta due volte e quindi $ 15+[-2(7)] $ stesso lavoro con i coefficienti
$ 1,-7,5 $
verifichiamo:
$ -7 \cdot 37+5 \cdot 52 =1 $
sul sito di MG trovi maggiori informazioni
http://www2.ing.unipi.it/~d9199/Home_Page/OT_Index.html
a=52
b=37
d=1
$ 52,0,1 $
52 è il nostro a, 0 è il coefficiente di 37 e 1 = coefficiente di 52
$ 37,1,0 $
37=b, 1 coefficiente di 37, e 0 quello di 52
$ 15,-1,1 $
vedo che 37 nel 52 ci sta al max una volta e quindi faccio $ a+[-1(b)] $ la stessa cosa lo faccio anche con i coefficienti
$ 7,3,-2 $
7 nel 15 sta due volte e quindi $ 15+[-2(7)] $ stesso lavoro con i coefficienti
$ 1,-7,5 $
verifichiamo:
$ -7 \cdot 37+5 \cdot 52 =1 $
sul sito di MG trovi maggiori informazioni
http://www2.ing.unipi.it/~d9199/Home_Page/OT_Index.html
Appassionatamente BTA 197!
$ (1026; 51)=3 $
$ 1026a+51b=3 $
e voglio trovare a e b interi
$ 1026,1,0 $
$ 51,0,1 $
guarda la serie dei numeri in colonne, la prima indica il numero, la seconda è la colonna di 1026 dove il numero o 1 o 0 sta a indicare la presenza o no della potenza $ 1026^1 $ e la terza è quello di 51, che indica la presenza di $ 51^1 $
$ 1026,1,0 $ perché notiamo che $ 1026=1 \cdot 1026^1 + 0 \cdot 51^1 $ cioè 1026 può essere scritto come la somma di una volta 1026 e 0 volte 51
$ 51,0,1 $ stesso ragionamento $ 51= 0 \cdot 1026^1 + 1 \cdot 51^1 $ dove 51 può essere scritto come la somma di 0 volte 1026 e 1 volta 51
la domanda da fare ora è: quante volte sta al max 51 in 1026?
20 volte
e quindi faccio$ 1026+[-20(51)] $ e viene 6
faccio la stessa cosa con le righe di numeri che avevo scritto
$ 1026,1,0 $
$ 51,0,1 $
noto che:
per la prima colonna $ 1026+[-20(51)]=6 $
per la seconda colonna ho 1 e 0 e quindi $ 1+[-20(0)]=1 $
la terza $ 0+[-20(1)]=-20 $
riscrivo la riga risultante
$ 6,1,-20 $
ora abbiamo
$ 1026,1,0 $
$ 51,0,1 $
$ 6,1,-20 $
facciamo ora lo stesso passaggio che abbiamo applicato alle prime due, però questa volta con le ultime due cioè 51 e 6
$ 51=6*8+3 \Rightarrow 3=51+[-8(6)] $
seconda colonna $ 0+[-8(1)]=-8 $
terza colonna $ 1+[-8(-20)]=161 $
e quindi
$ 3,-8,161 $
notiamo che 3 è proprio il numero cercato, nella seconda colonna (quella di 1026)c'è -8 e nella terza (quella di 51) c'è 161
e quindi 3 può essere scritto
$ 3=-8(1026) +161(51) $
dove -8 e 161 sono i numeri cercati
spero che mi sono spiegato questa volta...
(non sono tanto portato a spiegare... cmq sui video del senior stage, sezione "TdN" e non algebra dovrebbe esserci questa cosa...)
$ 1026a+51b=3 $
e voglio trovare a e b interi
$ 1026,1,0 $
$ 51,0,1 $
guarda la serie dei numeri in colonne, la prima indica il numero, la seconda è la colonna di 1026 dove il numero o 1 o 0 sta a indicare la presenza o no della potenza $ 1026^1 $ e la terza è quello di 51, che indica la presenza di $ 51^1 $
$ 1026,1,0 $ perché notiamo che $ 1026=1 \cdot 1026^1 + 0 \cdot 51^1 $ cioè 1026 può essere scritto come la somma di una volta 1026 e 0 volte 51
$ 51,0,1 $ stesso ragionamento $ 51= 0 \cdot 1026^1 + 1 \cdot 51^1 $ dove 51 può essere scritto come la somma di 0 volte 1026 e 1 volta 51
la domanda da fare ora è: quante volte sta al max 51 in 1026?
20 volte
e quindi faccio$ 1026+[-20(51)] $ e viene 6
faccio la stessa cosa con le righe di numeri che avevo scritto
$ 1026,1,0 $
$ 51,0,1 $
noto che:
per la prima colonna $ 1026+[-20(51)]=6 $
per la seconda colonna ho 1 e 0 e quindi $ 1+[-20(0)]=1 $
la terza $ 0+[-20(1)]=-20 $
riscrivo la riga risultante
$ 6,1,-20 $
ora abbiamo
$ 1026,1,0 $
$ 51,0,1 $
$ 6,1,-20 $
facciamo ora lo stesso passaggio che abbiamo applicato alle prime due, però questa volta con le ultime due cioè 51 e 6
$ 51=6*8+3 \Rightarrow 3=51+[-8(6)] $
seconda colonna $ 0+[-8(1)]=-8 $
terza colonna $ 1+[-8(-20)]=161 $
e quindi
$ 3,-8,161 $
notiamo che 3 è proprio il numero cercato, nella seconda colonna (quella di 1026)c'è -8 e nella terza (quella di 51) c'è 161
e quindi 3 può essere scritto
$ 3=-8(1026) +161(51) $
dove -8 e 161 sono i numeri cercati
spero che mi sono spiegato questa volta...
(non sono tanto portato a spiegare... cmq sui video del senior stage, sezione "TdN" e non algebra dovrebbe esserci questa cosa...)
Appassionatamente BTA 197!