La divisione euclidea o divisione con resto è intuitivamente quell'operazione che si fa quando si suddivide un numero a di oggetti in gruppi di b oggetti ciascuno e quindi si conta quanti gruppi sono stati formati e quanti oggetti sono rimasti. Il numero a si chiama dividendo, il numero b è il divisore, il numero di gruppi formati è il quoziente e il numero di oggetti rimanenti il resto.

La possibilità di operare una tale suddivisione per ogni dividendo e ogni divisore diverso dallo zero è stabilita dal seguente

Teorema

Questo significa che per ogni dividendo a e divisore b interi esiste solo una coppia di quoziente q e resto r (anch'essi interi) tali che sommando r con il prodotto di b per q si ottenga il dividendo a di partenza. Il resto r può assumere qualsiasi valore positivo (anche zero) strettamente minore di b.

• Se a = 7 e b = 3, si ha q = 2 e r = 1 ovvero 7 = 2 × 3 + 1.
• Se a = 7 e b = −3, si ha q = −2 e r = 1, ovvero 7 = (−2) × (−3) + 1.
• Se a = −7 e b = 3, si ha q = −3 e r = 2, ovvero −7 = (−3) × (3) + 2.
• Se a = −7 e b = −3, si ha q = 3 e r = 2, ovvero −7 = 3 × (−3) + 2.
• Se a = 3 e b = 7, si ha q = 0 e r = 3, ovvero 3 = 0 × 7 + 3.

Dimostrazione dell'esistenza.

Consideriamo l'insieme:

${\displaystyle S=\{a-nb\,|\,n\in \mathbb {Z} \,,\,a-nb\geq 0\}}$

Tale insieme è non vuoto infatti

se ${\displaystyle n=a}$ si ha

${\displaystyle a-nb=a-ab=a(1-b)}$

se ${\displaystyle n=-a}$ si ha

${\displaystyle a-nb=a+ab=a(1+b)}$

e poiché b≠0 almeno uno dei due prodotti deve essere non negativo.

Per il principio del buon ordinamento esiste un intero non negativo r che è il minimo di S, dunque per tale r esiste un numero intero q tale che

${\displaystyle r=a-qb}$

inoltre essendo r il minimo di S si deve avere r < | b |. Infatti se così non fosse avremmo che

${\displaystyle r'=r-|b|\geq 0}$

e che

${\displaystyle r'=r-|b|=(a-qb)-|b|=a-\left(q+{\frac {|b|}{b}}\right)b}$

dunque r' sarebbe in S, ma poiché è più piccolo di r, che è il minimo, siamo giunti ad un assurdo.

Dimostrazione dell'unicità

Supponiamo che ci siano due coppie ${\displaystyle (q,r)}$ e ${\displaystyle (q',r')}$ tali che:

${\displaystyle a=bq+r,\qquad 0\leq r<|b|}$

${\displaystyle a=bq'+r',\qquad 0\leq r'<|b|}$

allora si ha

(*) ${\displaystyle r-r'=-(q-q')b}$

inoltre poiché r e r' sono positivi e minori di | b |:

${\displaystyle r-r'\leq r<|b|}$

${\displaystyle r'-r\leq r'<|b|}$

quindi da (*) si ricava

${\displaystyle |q-q'|\cdot |b|\leq |r-r'|<|b|}$

ovvero

${\displaystyle |q-q'|<1}$

e poiché si tratta di un numero intero e positivo:

${\displaystyle |q-q'|=0}$

e quindi, da (*) si deduce anche

${\displaystyle r-r'=0}$

cioè le coppie sono uguali.

L'idea della divisione con resto può essere estesa in altre strutture algebriche, come l'anello dei polinomi. Viene chiamato anello euclideo un anello in cui vale una versione generale della divisione euclidea.

Lo stesso argomento in dettaglio: Aritmetica modulare.

La divisione euclidea è alla base dell'aritmetica modulare. Fissato un intero n possiamo suddividere l'insieme dei numeri interi in n classi (sottoinsiemi) a seconda del resto che danno una volta divisi per n. In altre parole, si definisce la seguente relazione di equivalenza: si dice che un intero a è equivalente a b modulo n se e solo se la differenza a-b è un multiplo di n. Le classi di equivalenza di ${\displaystyle \mathbb {Z} }$,

${\displaystyle [0],[1],...,[n-2],[n-1]}$

rispetto a tale relazione di equivalenza formano un anello.

A volte con divisione intera viene indicata l'operazione (indicata con il segno ${\displaystyle \setminus }$) definita dalla seguente relazione ${\displaystyle a\setminus b=\lfloor a/b\rfloor }$. La notazione ${\displaystyle \lfloor x\rfloor }$ indica la funzione parte intera di ${\displaystyle x}$.^[1]

Questa operazione viene talvolta indicata nei software di calcolo anche come div. Tuttavia come per altre operazioni occorre sempre controllare le specifiche del programma perché con il simbolo div viene indicata anche un altro tipo di divisione intera basata sulla operazione di troncamento e non sull'operazione parte intera.^[2]

• Divisibilità
• Anello euclideo
• Parte intera
• Aritmetica modulare

• Wikimedia Commons contiene immagini o altri file sulla divisione euclidea

• divisione euclidea, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica