Esistenza e unicità della divisione euclidea

Teorema

Siano $n,m\in \mathbb{Z}$ con $m\ne 0.⟹\mathrm{\exists }!q,r\in \mathbb{Z}:$

$\{\begin{array}{l}n=qm+r\\ 0\le r<|m|\end{array}$

Inoltre $q,m\in \mathbb{N}\text{ se }n,m\in \mathbb{N}$

Dimostrazione

Esistenza

Ipotizziamo che $n,m\in \mathbb{N}$ e procediamo per induzione di seconda forma su $n$.

$n=0$ (BASE DELL'INDUZIONE)
È sufficiente porre $q,r=0$

$n\ge 1,\mathrm{\forall }k<n⟹n$ (PASSO INDUTTIVO)

Supponiamo $n>0$ e che la tesi sia vera per ogni $k<n$.

• Se $n<m$, poniamo $q=0,r=n$.
• Altrimenti, avremo che $n\ge m$. Sia $k=n-m$.
  Applicando la divisione euclidea, otteniamo che:

Ma allora $n=k+m=mq+r+m=(q+1)m+r.$

• Analizziamo ora il caso opposto, ovvero quando $n<0$.
  Se $m>0$, applicando la divisione euclidea a $-n>0,m>0$, vale:

Se $r=0$ abbiamo finito, altrimenti continuiamo per ottenere un resto > 0.
Aggiungendo e togliendo $m$:

dove $m-r$ è strettamente positivo per definizione.

• Sia infine $m<0$, ovvero $-m>0$.

Unicità

Sia

Proviamo che $q=q^{\prime },r=r^{\prime }$.
Allora vale:
$\begin{array}{r}n=qm+r=q^{\prime }m+r^{\prime }\iff qm-q^{\prime }m=r^{\prime }-r\iff (q-q^{\prime })m=r^{\prime }-r\iff |q-q^{\prime }||m|=|r-r^{\prime }|\end{array}$

$⟹|q-q^{\prime }||m|=|r-r^{\prime }|<|m|$
$⟹|q-q^{\prime }|<1$

Concludiamo che $q^{\prime }-q=0⟹q^{\prime }=q$.
Dall'equazione originale ricaviamo che: $\cancel{mq}+r=\cancel{m{q}^{\prime }}+r^{\prime }⟹r^{\prime }=r$.