[AIUTO] Identità di Bezòut

[D4rkAng3l]

Ciao,
stò impazzendo nel tentar di capire le identità di bezout.

Da quello che ho capito è un modo per riscrivere l'MCD tra due numeri (a,b) nella forma: MCD(a,b) = ALPHA*a + BETA*b

Da quello che ho capito io partendo dall'algoritmo euclideo per ricavare l'MCD(a,b) posso sempre trovare un'identita di Bezòut per ogni MCD.

ALGORITMO EUCLIDEO PER MCD(a,b) a>=b

1) a = b*q1 + r1
2) b = r1*q2 + r2
3) r1 = r2*q3 + r3
........................
i) ri = ri + qi+2 * ri+2

L'MCD è l'ultimo resto non nullo....

Ora per trovarmi un'identita di bezòut per l'MCD(a,b) devo mostrare che tutti i resti delle divisioni si possono scrivere come combinazioni di a e b e devo poter ottenere qualcosa del tipo ALPHA*a+BETA*B

Inizio a considerare r1 che posso riscriverlo come:
r1 = a-b*q e questo è di per se una combinazione di a e di b (volendo posso considerarlo r1 = (1)*a + (-q)*b

Poi passpo a considerare r2:

r2 = b - r1q2 SOSTITUISCO r1 in questa formula con il valore precedentemente trovato e ottengo: r1 = b - (a-b*q1)*q2 da cui
r2 = b - a*q2 + b*q1*q2 = (-q2)*a + (1 + q1*q2)*b


Considero ora r3:

r3 = r1 - r2*q3
Sostituisco ora nella formuala i valori di r1 ed r2 precedentemente trovati:

r3 = (a - b*q1) - (b - r1*q2)*q3
SOSTITUISCO ORA IL VALORE DI r1
r3 = (a - b*q1) - [b - (a-b*q1)*q2]
r3 = a - b*q1 - b*q3 + a*q2*q3 - b*q1*q2*q3
r3 = = (1+q2*q3)*a + (-q1 - q3 - q1*q2*q3)*b

Continuo ad andare avanti così finchè non arrivo a calcolarmi l'MCD e questa sarà un'identità di Bezòut per l'MCD

Si fà così?

Grazie
Andrea

[shinji_85]

Oddio... Ricordo qualcosa riferito scorso anno e che ha a che fare con "Algebra e Logica"... Ma non di preciso cosa indicasse 'st'identità...


E mi si stanno intrecciando gli occhi a leggere tutto il tuo post...


Prova a partire da un esempio... Che non dev'essere nulla di difficile, per quanto ricordi...

[Ziosilvio]

Originariamente inviato da D4rkAng3l

stò impazzendo nel tentar di capire le identità di bezout.

Da quello che ho capito è un modo per riscrivere l'MCD tra due numeri (a,b) nella forma: MCD(a,b) = ALPHA*a + BETA*b

Esatto.
Il Teorema di Bézout dice proprio che, se a e b sono interi, allora esistono interi x e y tali che MCD(a,b)=ax+by; inoltre, MCD(a,b) è il minimo intero positivo che si può ottenere in questo modo, con x e y entrambi interi.

Da quello che ho capito io partendo dall'algoritmo euclideo per ricavare l'MCD(a,b) posso sempre trovare un'identita di Bezòut per ogni MCD.

ALGORITMO EUCLIDEO PER MCD(a,b) a>=b

1) a = b*q1 + r1
2) b = r1*q2 + r2
3) r1 = r2*q3 + r3
........................
i) ri = ri + qi+2 * ri+2

L'ultima riga contiene una svista: dovrebbe essere r[i]=r[i+1]*q[i+2]*r[i+2].

L'MCD è l'ultimo resto non nullo....

Esatto.

Ora per trovarmi un'identita di bezòut per l'MCD(a,b) devo mostrare che tutti i resti delle divisioni si possono scrivere come combinazioni di a e b e devo poter ottenere qualcosa del tipo ALPHA*a+BETA*B

Inizio a considerare r1 che posso riscriverlo come:
r1 = a-b*q e questo è di per se una combinazione di a e di b (volendo posso considerarlo r1 = (1)*a + (-q)*b

Infatti si fa proprio così.

Poi passpo a considerare r2:

r2 = b - r1q2 SOSTITUISCO r1 in questa formula con il valore precedentemente trovato e ottengo: r1 = b - (a-b*q1)*q2 da cui
r2 = b - a*q2 + b*q1*q2 = (-q2)*a + (1 + q1*q2)*b


Considero ora r3:

r3 = r1 - r2*q3
Sostituisco ora nella formuala i valori di r1 ed r2 precedentemente trovati:

r3 = (a - b*q1) - (b - r1*q2)*q3
SOSTITUISCO ORA IL VALORE DI r1
r3 = (a - b*q1) - [b - (a-b*q1)*q2]
r3 = a - b*q1 - b*q3 + a*q2*q3 - b*q1*q2*q3
r3 = = (1+q2*q3)*a + (-q1 - q3 - q1*q2*q3)*b

Continuo ad andare avanti così finchè non arrivo a calcolarmi l'MCD e questa sarà un'identità di Bezòut per l'MCD

Si fà così?

Sì.

[D4rkAng3l]

Originariamente inviato da Ziosilvio

Esatto.
Il Teorema di Bézout dice proprio che, se a e b sono interi, allora esistono interi x e y tali che MCD(a,b)=ax+by; inoltre, MCD(a,b) è il minimo intero positivo che si può ottenere in questo modo, con x e y entrambi interi.

L'ultima riga contiene una svista: dovrebbe essere r[i]=r[i+1]*q[i+2]*r[i+2].

Esatto.

Infatti si fa proprio così.

Sì.

Grazie ZioSilvio...sei sempre preparatissimoooooooooooooooo !!! heheh mi sono appena visto la storiella della sostituzione di a con la coppia (1,0) e di b con la coppia (0,1)...simpatica come cosa....dici che è normale che non avendo seguito la lezione c'ho messo tipo 3 giorni a capire Bezòut o sono un po' tardo? :-/

[FabryB]

Per fortuna che ti hanno risposto, che mi stava per venire voglia di rispolverare matematica discreta per spiegartela, fhiuuh... per poco..

[Ziosilvio]

Originariamente inviato da D4rkAng3l

dici che è normale che non avendo seguito la lezione c'ho messo tipo 3 giorni a capire Bezòut o sono un po' tardo?

Ti dirò che anche per me, la prima volta che ho visto l'Identità di Bézout (corso di Algebra, primo anno, laurea in Matematica), è stato un po' uno shock.
Credo dipenda anche dal fatto che alle superiori si viene abituati al fatto che il MCD viene presentato come il massimo di un insieme, mentre si accenna di rado al fatto che il massimo di un insieme possa essere anche il minimo di un altro insieme.

[D4rkAng3l]

Originariamente inviato da Ziosilvio

Ti dirò che anche per me, la prima volta che ho visto l'Identità di Bézout (corso di Algebra, primo anno, laurea in Matematica), è stato un po' uno shock.
Credo dipenda anche dal fatto che alle superiori si viene abituati al fatto che il MCD viene presentato come il massimo di un insieme, mentre si accenna di rado al fatto che il massimo di un insieme possa essere anche il minimo di un altro insieme.

hehe io stò ad informatica e non me l'hanno spiegato nel corso di algebra (prossimo semestre) ma in matematica discreta...il libro però è un libro di algebra scritto dalla mia proff...sai che differenza c'è tra algebra e matematica discreta?

Ciao
Andrea

[FabryB]

Originariamente inviato da D4rkAng3l

hehe io stò ad informatica e non me l'hanno spiegato nel corso di algebra (prossimo semestre) ma in matematica discreta...il libro però è un libro di algebra scritto dalla mia proff...sai che differenza c'è tra algebra e matematica discreta?

Ciao
Andrea

Discreta è più per l'informatica, ma non so che differenza cè, sono argomenti separati.
Anche io ho usato il libro che aveva scritto il prof, cosi uno non rischia di studiare di più. Ma quanti libri scrive sta gente?