La divisione euclidea
Dati due interi a e b con b≠0, allora esistono due interi q e r detti rispettivamente quoziente e resto, tali che $$ a=b \cdot q + r $$
Il resto è un numero intero compreso tra 0 e il valore assoluto |b|.
$$ 0 \le r < |b| $$
Se il resto è nullo, allora a è un divisore di b.
Un esempio pratico
Ho due interi a=3 e b=8.
L'elemento a=3 non è un divisore di b=8.
Quindi, la divisione 8/3 genera un resto r=2.
$$ b = a \cdot q + r \\ 8 = 3 \cdot q + r \\ 8 = 3 \cdot 2 + 2 $$
Il quoziente della divisione è q=2 con resto r=2.
Il resto è un intero positivo compreso tra 0 e |8|.
Dimostrazione e spiegazione
Dimostrazione di esistenza
Ho un insieme composto dagli elementi a-nb =>0 per qualsiasi n∈Z
$$ S = \{ a-nb \:\: | \:\: n \in Z , a-nb \ge 0 \} $$
Si tratta di un insieme non vuoto perché per n=a si ha
$$ a-nb = a-ab = a(1-b) $$
mentre per n=-a si ha
$$ a-nb = a-(-a)b = a(1+b) $$
Essendo b≠0, in almeno uno dei due casi l'elemento a è positivo e l'elemento appartiene all'insieme N.
Esempio. Per ipotesi fisso a=3 e b=5. Devo verificare se esiste almeno un elemento appartenente a S={a-nb≥0}. $$ S=\{ a-nb \} = \{ 3-n \cdot 5 \ge 0 \} $$ Per n=a=3 $$ 3-n \cdot 5 = 3- 3 \cdot 5 = -12 $$ Mentre per n=-a=-3 $$ 3-n \cdot 5 = 3-(-3) \cdot 5 = 18 \ge 0 $$ Preso n=a in almeno un caso l'espressione è soddisfatta. Quindi il sottoinsieme S non è vuoto.
L'insieme S ha sicuramente un elemento minimo (r) per qualche intero q∈Z.
$$ r = a - qb $$
Devo provare che qualsiasi resto sia r<|b|
Per assurdo ipotizzo che
$$ r > |b| $$
Quindi
$$ r - |b| > 0 $$
Per semplificare i calcoli chiamo questo elemento r'
$$ r' = r - |b| > 0 $$
Quindi sostituisco r=a-qb
$$ r' = r - |b| > 0 $$
$$ r' = (a-qb) - |b| > 0 $$
e con qualche passaggio algebrico ottengo una forma equivalente
$$ r' = a - (q + \frac{|b|}{b} ) b > 0 $$
Considerando q'=q+|b|/b
$$ r' = a - q' b > 0 $$
Pertanto anche r' appartiene a S.
$$ r' \in S $$
Tuttavia, questo è impossibile perché r' è minore di r
$$ r' = r - |b| \Rightarrow r' < r $$
Ma essendo r il minimo dell'insieme S, questa conclusione è impossibile.
Pertanto, il resto r deve essere necessariamente minore di |b|.
Dimostrazione di unicità
Per ipotesi assurda esistono due coppie (q,r) e (q',r') di S tali che
$$ a=bq+r , 0 \le r < |b| $$
$$ a=bq'+r' , 0 \le r' < |b| $$
Entrambe i resti r e r' sono numeri positivi minori di |b|
$$ 0 \le r,r' < |b| $$
Se per ipotesi r'≥r allora
$$ 0 \le r'-r \le r' < |b| $$
Poiché
$$ r'-r = a-bq' - (a-bq) $$
$$ r'-r = -bq' + bq = b(q-q') $$
Posso riscrivere
$$ 0 \le r'-r \le r' < |b| $$
$$ 0 \le b(q-q') \le r' < |b| $$
Poiché b è non negativo per definizione, lo metto sotto valore assoluto |b|
$$ 0 \le |b| \cdot (q-q') \le r' < |b| $$
Sapendo che |b|·(q-q')≥0 e r'<|b|, la relazione è soddisfatta soltanto se q-q'<1.
Trattandosi di numeri interi, l'unica possibilità è q-q'=0 ossia q=q'
$$ 0 \le |b| \cdot 0 \le r' < |b| $$
Infine, se i quozienti sono uguali
$$ q = q' $$
allora anche i resti devono essere uguali
$$ r=r' $$
Nota. Se q=q' allora $$ a=bq+r $$ $$ a=bq+r' $$ Mettendo in evidenza r e r' ottengo $$ r=a-bq $$ $$ r'=a-bq $$ ossia $$ r=r' $$
Questo dimostra l'unicità del quoziente e del resto nella divisione dei numeri interi.
E così via
