Algoritmo delle divisioni successive

[davi2892]

Ragazzi buonasera... Qualcuno potrebbe indirizzarmi ad una giusta dimostrazione di questo teorema... CI sto sbattendo la testa da stamattina e non riesco a comprenderlo. Grazie anticipatamente .

[francicko]

Credo che tu ti riferisca al ben noto algoritmo di euclide, che altro non è che un procedimento di calcolo, appunto per divisioni successive, che permette l'effettiva determinazione del massimo comun divisore $(a,b)$ con $a$, $b$ interi non
entrambi nulli, ed essendo solo , come detto già sopra un procedimento di calcolo per operazioni successive, non c'è nulla
da dimostrare.

[davi2892]

Il mio libro lo definisce mediante il seguente teorema: "Siano a e b numeri interi relativi non nulli. Allora esiste un MCD di a e di b e risulta d= au+bv,per opportuni interi u e v. Se qualche mod mi autorizza,posso postare anche una screen della pagina.

[Sk_Anonymous]

"davi2892":Il mio libro lo definisce mediante il seguente teorema: "Siano a e b numeri interi relativi non nulli. Allora esiste un MCD di a e di b e risulta d= au+bv,per opportuni interi u e v. Se qualche mod mi autorizza,posso postare anche una screen della pagina.

Questa è l'identità di Bézout.

[gundamrx91-votailprof]

Una dimostrazione dell'esistenza e dell'unicità del $MCD$ è la seguente:

Siano $a,b in ZZ, a,b !=0$, allora il $MCD(a,b)$ esiste ed è unico.

Esistenza

Sia $S:=(aZZ+bZZ) nn NN\\{0} = {ax+by>0 |AAx,y in ZZ}!=O/$
Se $a>0 ^^ b=0 => a*1+b*0=a in S$
Se $a<0 ^^ b=0 => a*(-1)+b*0=-a in S$
Se $a=0 ^^ b>0 => a*0+b*1=b in S$
Se $a=0 ^^ b<0 => a*0+b(-1)=-b in S$

Per il principio del buon ordinamento (ogni insieme dotato di relazione d'ordine ha minimo) sia $d=ax_0+by_0>=1$ il minimo di $S$, per $AAx_0,y_0 in ZZ$, allora si deve verificare che $d=MCD(a,b)$, cioè che $d|a ^^ d|b ^^ (EEc in ZZ$ tale che $c|a ^^ c|b => c|d)$.
Preso un qualsiasi intero di $S$ nella forma $ax+by$ lo si divida per $d$, esistono allora due interi $q,r in ZZ$ tali che
$ax+by=qd+r$ con $0<=r Se fosse $r d|a ^^ d|b$, $AAx,y in ZZ$.
Infine per ipotesi $c|a ^^ c|b => c|ax_0+by_0$, quindi $c|d$.

Unicità
Siano per ipotesi $d,d^{\prime} in ZZ$ due $MCD(a,b)$, allora:

$d|d^{\prime}$: dal fatto che $d^{\prime}=MCD(a,b)$ e da $d|a ^^ d|b => d|d'$
$d^{\prime}|d$: dal fatto che $d=MCD(a,b)$ e da $d^{\prime}|a ^^ d^{\prime}|b => d^{\prime}|d$

[davi2892]

"GundamRX91":Una dimostrazione dell'esistenza e dell'unicità del $MCD$ è la seguente:

Siano $a,b in ZZ, a,b !=0$, allora il $MCD(a,b)$ esiste ed è unico.

Esistenza

Sia $S:=(aZZ+bZZ) nn NN\\{0} = {ax+by>0 |AAx,y in ZZ}!=O/$
Se $a>0 ^^ b=0 => a*1+b*0=a in S$
Se $a<0 ^^ b=0 => a*(-1)+b*0=-a in S$
Se $a=0 ^^ b>0 => a*0+b*1=b in S$
Se $a=0 ^^ b<0 => a*0+b(-1)=-b in S$

Per il principio del buon ordinamento (ogni insieme dotato di relazione d'ordine ha minimo) sia $d=ax_0+by_0>=1$ il minimo di $S$, per $AAx_0,y_0 in ZZ$, allora si deve verificare che $d=MCD(a,b)$, cioè che $d|a ^^ d|b ^^ (EEc in ZZ$ tale che $c|a ^^ c|b => c|d)$.
Preso un qualsiasi intero di $S$ nella forma $ax+by$ lo si divida per $d$, esistono allora due interi $q,r in ZZ$ tali che
$ax+by=qd+r$ con $0<=r Se fosse $r d|a ^^ d|b$, $AAx,y in ZZ$.
Infine per ipotesi $c|a ^^ c|b => c|ax_0+by_0$, quindi $c|d$.

Unicità
Siano per ipotesi $d,d^{\prime} in ZZ$ due $MCD(a,b)$, allora:

$d|d^{\prime}$: dal fatto che $d^{\prime}=MCD(a,b)$ e da $d|a ^^ d|b => d|d'$
$d^{\prime}|d$: dal fatto che $d=MCD(a,b)$ e da $d^{\prime}|a ^^ d^{\prime}|b => d^{\prime}|d$

Esattamente...è proprio questa. GRAZIE!