Problema con bezout

[dottorkame]

In un esercizio di matematica discreta c' e' scritto di trovare il MCD tra 273 e 520 col metodo di euclide, il risultato e' 13.

poi pero mi chiedono di trovare 2 numeri interi x e y tali che d=xa+yb ==> d = x * 520 + y * 273.
per risolverlo dovrei utilizzare l' identita di bezout, qualcuno mi puo spiegare come si fa quest' esercizio?

[robydream]

Originariamente inviato da dottorkame
In un esercizio di matematica discreta c' e' scritto di trovare il MCD tra 273 e 520 col metodo di euclide, il risultato e' 13.

poi pero mi chiedono di trovare 2 numeri interi x e y tali che d=xa+yb ==> d = x * 520 + y * 273.
per risolverlo dovrei utilizzare l' identita di bezout, qualcuno mi puo spiegare come si fa quest' esercizio?

Buonasera.

Posto che abbia ben compreso la domanda la soluzione é

n1 = 273
n2 = 520

MCD(n1,n2) = 13
mcm(n1,n2) = 10920

Identità di Bezout: (-19) n1 + (10)n2 = 13

Saluti

[dottorkame]

Originariamente inviato da robydream
Buonasera.

Posto che abbia ben compreso la domanda la soluzione é

n1 = 273
n2 = 520

MCD(n1,n2) = 13
mcm(n1,n2) = 10920

Identità di Bezout: (-19) n1 + (10)n2 = 13

Saluti

Il mio problema e' come si fann atrovare -19 e 10?

[robydream]

Originariamente inviato da dottorkame
Il mio problema e' come si fann atrovare -19 e 10?

Ciao. ti scrivo una breve dimostrazione, con la quale non avrai problemi a risolvere:

Il teorema di Bézout si dimostra come corollario di un altro teorema: il Teorema di Esistenza ed Unicità del Massimo Comun Divisore.

Teorema
Dati comunque a, b appartenenti a Z, non entrambi nulli, esiste ed è unico l'intero naturale d := MCD(a, b).
d coincide con il minimo intero positivo nell'insieme:
S := {ax + by : x ,y appartengono a Z, ax + by > 0}.

Tralsciandi questa dim. e ritornando all'identità di Bézout questa può essere enunciata come corollario del precedente teorema:

Corollario (Identità di Bézout)
Dati comunque a, b appartenenti a Z, non entrambi nulli, esistono x0,y0 appartenenti a Z in modo che si abbia:
MCD(a, b) = ax0 + by0

Dimostrazione.
Per come è fatto l'insieme S (nell'enunciato del teorema precedente) d = min S, quindi d appartiene ad S e quindi esistono x0 e y0 tali che d = ax0 + by0.


Esiste anche una dimostrazione diretta di questo secondo teorema, basata sul fatto che il resto delle divisioni euclidee successive tra due numeri naturali può sempre essere scritto come combinazione del dividendo e del divisore. In dettaglio: supponiamo a < b, in modo che sia b = qa + r con q > 0; si ha allora anche ovviamente r = b - qa con r < a. Si divida ora a per r: si ottiene a = q'r + r' e quindi r' = a - q'r = (1 - qq')a - q'b. Si prosegue allora dividendo r per r', e così via.

Dal momento che a ogni divisione successiva il resto continua a diminuire, questo procedimento (noto come algoritmo di Euclide) termina solo quando si ottiene una divisione esatta (cioè con resto zero). Si può verificare che il resto ottenuto nel penultimo "passo" è proprio il MCD di a e b, notando che qualsiasi numero che divide a e b divide anche tutti i resti ottenuti con questo algoritmo e che d'altra parte (come si vede "giocando" ancora con le espressioni delle divisioni effettuate) ogni resto ottenuto con questo algoritmo è multiplo del penultimo.


Saluti