...dimostrazione identità di Bèzout...
Buongiorno a tutti.
Riporto il testo dell'esercizio.
Dati $a$ $b$ interi,supponiamo che $1$ sia combinazione lineare di $a$ $b$.
Dimostrare che $mcd(a,b)=1$
Suggerimenti?
Riporto il testo dell'esercizio.
Dati $a$ $b$ interi,supponiamo che $1$ sia combinazione lineare di $a$ $b$.
Dimostrare che $mcd(a,b)=1$
Suggerimenti?
Risposte
Il massimo comun divisore di a e b divide ogni combinazione lineare di a e b...
Si ok,questo lo sapevo,ma devo dimostrarlo...
@Pozzetto: Per favore, ragiona sui suggerimenti prima di rispondere.
Posso dire quanto segue?
Se $d$ è un divisore comune di $a,b$ allora $d$ divide ogni combinazione lineare di $a,b$ in particolare $d|a$ e $d|b$
???
Se $d$ è un divisore comune di $a,b$ allora $d$ divide ogni combinazione lineare di $a,b$ in particolare $d|a$ e $d|b$
???
Insomma, supponendo che [tex]$d|a$[/tex] e [tex]$d|b$[/tex] ricavi che [tex]$d|a$[/tex] e [tex]$d|b$[/tex]...
Te l'ho detto, rifletti bene.
Se hai tra le ipotesi che [tex]$1$[/tex] è una combinazione di [tex]$a$[/tex] e [tex]$b$[/tex], ciò ti dovrà pur servire a qualcosa.
Te l'ho detto, rifletti bene.
Se hai tra le ipotesi che [tex]$1$[/tex] è una combinazione di [tex]$a$[/tex] e [tex]$b$[/tex], ciò ti dovrà pur servire a qualcosa.
ma quindi quello che ho detto io non va bene?
Non si può concludere con quanto detto?
Non si può concludere con quanto detto?
No. Devi pensarci meglio.
Il suggerimento che ti è stato dato è il seguente: se [tex]a,b\in\mathbb{Z},\;\; d=(a,b)[/tex], allora [tex]a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}[/tex]. Questa uguaglianza tra insiemi (che si può facilmente provare per doppia inclusione), dovrebbe aiutarti a concludere...
Ma scusate, perchè fare le cose così complicate?
Se [tex]$d|a$[/tex] e [tex]$d|b$[/tex], allora per ogni [tex]$n,m\in \mathbb{Z}$[/tex] si ha [tex]$d|a\ n+b\ m$[/tex]; visto che esistono [tex]$\nu,\mu\in \mathbb{Z}$[/tex] tali che [tex]$a\ \nu+b\ \mu =1$[/tex], per quanto appena detto si ha [tex]$d|1$[/tex], ergo...
Se [tex]$d|a$[/tex] e [tex]$d|b$[/tex], allora per ogni [tex]$n,m\in \mathbb{Z}$[/tex] si ha [tex]$d|a\ n+b\ m$[/tex]; visto che esistono [tex]$\nu,\mu\in \mathbb{Z}$[/tex] tali che [tex]$a\ \nu+b\ \mu =1$[/tex], per quanto appena detto si ha [tex]$d|1$[/tex], ergo...
pozzetto non hai capito che devi dimostrarlo che il MCD(a,b) divide ogni comb lineare di a e b.
E poi usando questo puoi dire che MCD(a,b) divide 1 e quindi è proprio 1
in pratica l'enunciato che devi dimostrare è questo
$ AA a,b,c in ZZ, EE x,y in ZZ : ax+bc=c <=> MCD(a,b)|c $
a te serve la parte $ => $ del teorema
(cioè sai che esistono a b e 1 tali che ax+by=1. Per questo teorema hai che MCD(a,b)|1 cioè MCD=1 per la positività
La dimostrazione dell'enunciato sopra non è difficile, dovresti probare a farla da solo... però posso scriverti una traccia ma guardala dopo averci provato..
dim:
$=>$) (molto facile, basta usare la def di MCD)
Sia $d=MCD(a,b)$ . Allora per def di MCD, $d|a$ e $d|b$ ovvero per def di divisibilità $a=dh$ e $b=dk$.
allora $dhx+dky=c$ cioè $d|c$.
$lArr$) Richiede Bezout
$d|c$ allora $dk=c$ per def di divisibilità
per Bezout
esistono t e s tali che $at+bs=d$
moltiplicando entrambi i membri dell'ultima per k ottengo che
$atk+bsk=dk$
quindi esistono x=tk e y=sk tali che vale
$ax+by=c
fine
E poi usando questo puoi dire che MCD(a,b) divide 1 e quindi è proprio 1
in pratica l'enunciato che devi dimostrare è questo
$ AA a,b,c in ZZ, EE x,y in ZZ : ax+bc=c <=> MCD(a,b)|c $
a te serve la parte $ => $ del teorema
(cioè sai che esistono a b e 1 tali che ax+by=1. Per questo teorema hai che MCD(a,b)|1 cioè MCD=1 per la positività
La dimostrazione dell'enunciato sopra non è difficile, dovresti probare a farla da solo... però posso scriverti una traccia ma guardala dopo averci provato..
dim:
$=>$) (molto facile, basta usare la def di MCD)
Sia $d=MCD(a,b)$ . Allora per def di MCD, $d|a$ e $d|b$ ovvero per def di divisibilità $a=dh$ e $b=dk$.
allora $dhx+dky=c$ cioè $d|c$.
$lArr$) Richiede Bezout
$d|c$ allora $dk=c$ per def di divisibilità
per Bezout
esistono t e s tali che $at+bs=d$
moltiplicando entrambi i membri dell'ultima per k ottengo che
$atk+bsk=dk$
quindi esistono x=tk e y=sk tali che vale
$ax+by=c
fine
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo