Siano $a_1,...,a_n$ interi non tutti nulli. Posto $d=M.C.D.(a_1,...,a_n)$ risulta
d è il minimo numero naturale del tipo $a_1x_1+....a_nx_n$ con ogni $x_i in ZZ$
Prima di iniziare la lettura, quello che è in corsivo l'ho aggiunto io "dimostra l'affermazione precedente".
Dimostrazione:
Sia $S={a_1x_1+....a_nx_n\:\ x_i in ZZ\,\ a_1x_1+....a_nx_n ge 1}$.
Risulta $S ne emptyset$ infatti esistono necessariamente $x_i in ZZ$ e $a_1,...,a_n in ZZ$ tali che $a_1x_1+....a_nx_n ge 1.$
Sia $m=a_1y_1+a_2y_2+...+a_ny_n=minS$ è multiplo di ogni divisore comune alle $a_i.$
Infatti, considero un generico divisore comune $z$, alle $a_i$.
Ricordo che se $c$ è un divisore comune di $a $ e di $b$ allora $c$ divide anche $ah+bk$ con $h,l in ZZ$.
Quindi generalizzando si ha che se $z$ divide $a_1,a_2,..., a_n$ allora $z$ divide anche $a_1y_1+a_2y_2+...+a_ny_n$ per qualche $y_1,y_2,...,y_n in ZZ$.
Per cui risulta
$m=a_1y_1+a_2y_2+...+a_ny_n=z(c_1y_1+c_2y_2+...+c_ny_n), \ c_i in ZZ $
Allora essendo è un multiplo di ogni divisore comune lo è per $d$, quindi $m ge d$
Per l'algoritmo della divisione euclidea abbiamo che $a_i=mq_i+r_i$ dove $q_i,r_i in ZZ$ e $0 le r_i < m$, quindi risulta
$0 le r_i=a_i-mq_i<m$
a causa dell'essere $m=minS$ segue che $r_i=0$. Allora $a_i=mq_i$ quindi $m$ divide ogni $a_i$, quindi per definizione di $M.C.D.$ si ha $m ge d$. Da quello di prima si ha $m=d$
La parte che non mi è chiara è quella in grassetto. Mi spiego meglio abbiamo supposto che $m=minS$ quindi $m in S$ e $y ge m ge 1\,\ forall y in S$. Adesso non so numericamente quanto vale $m$ può valere $1,4,6,10,...,1000$ e cosi via, quindi se ho capito bene $r_i=0 $ in quanto dovrebbe risultare minore di $1$, però come detto, non sono sicuro se vale $0 le r_i=a_i-mq_i<1 le m$, quindi senz'altro $r_i=0$
Grazie.