divisione euclidea

Teorema

Siano $a,b\in \mathbb{Z}$; $b\ne 0$, allora esistono $q,r\in \mathbb{Z}$ con $0\le r<|b|$ tali che $a=qb+r$. Inoltre $q$, $r$ sono unici.

Dimostrazione

Sia $S=\{a-nb\mid n\in \mathbb{Z},a-nb\ge 0\}$.

Abbiamo $S\ne \varnothing$. Definiamo $r=\min S$. $r$ così definito soddisfa la prima parte della tesi. Inoltre se $q$ è tale che $(a-qb)=r$ otteniamo $a=qb+r$.

Per dimostrare l’unicità supponiamo che esista una seconda espressione $a=\overline{q}b+\overline{r}$. Avremmo che $[qb+r=\overline{q}b+\overline{r}]\Rightarrow |b||q-\overline{q}|=|r-\overline{r}|$. Ricordando che per ipotesi $r,\overline{r}<|b|$ otteniamo la maggiorazione:

$|b||q-\overline{q}|<|b|$ che implica, sfruttando la cancellazione in $\mathbb{N}$ (la quale è ereditata da $\mathbb{Z}$), $|q-\overline{q}|<1$. Essendo $|q-\overline{q}|\in \mathbb{N}$ si conclude che $|q-\overline{q}|=0$. Ritornando ora all’equazione $|b||(q-\overline{q})|=|r-\overline{r}|$ concludiamo che pure $|r-\overline{r}|=0$.

Osservazione

Dati due numeri $a,b\in \mathbb{Z}$, l’insieme $D=\{d:d|a\text{ e }d|b\}$ dei divisori di $(a,b)$ è uguale all’insieme $\Delta =\{\delta :\delta |(a-b)\text{ e }\delta |b\}$ dei divisori di $(a-b,b)$.

Infatti preso un divisore $d\in D$ si ha: $a=t_{1}d$, $b=t_{2}d$.
Allora $a-b=t_{1}d-t_{2}d=(t_1-t_2)d$, cioè $d$ divide $a-b$.

Viceversa preso un divisore $\delta \in \Delta$, si ha $a-b={\tau }_1\delta$, $b={\tau }_2\delta$. Allora
$a=a-b+b={\tau }_1\delta +{\tau }_2\delta =({\tau }_1+{\tau }_2)\delta$, cioè $\delta$ divide $a$.

In particolare $MCD(a,b)=\max D=\max \Delta$. E dunque $MCD(a,b)=MCD(a-b,b)$. Per di più, ponendo $a=q_{0}b+r_0$, e applicando ripetutamente questo risultato otteniamo:

$$MCD(a,b)=MCD(a-b,b)=MCD(a-2b,b)=\cdots =MCD(a-q_{0}b,b).$$

Dunque $MCD(a,b)=MCD(r_0,b)$ dove $r_0$ è il resto della divisione euclidea e si ha $0\le r_0<|b|$.

Risorse