Divisione euclidea

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

Dati due interi a e b con b≠0 esiste un'unica coppia di interi q ed r detti quoziente e resto tali che:

a = b × q + r
0 ≤ r < | b |

dove | b | indica il valore assoluto del divisore.

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.

Esempi

  • 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

Dimostrazione dell'esistenza.

Consideriamo l'insieme:

S = { a − n b | n ∈ Z , a − n b ≥ 0 } {\displaystyle S=\{a-nb\,|\,n\in \mathbb {Z} \,,\,a-nb\geq 0\}}

Tale insieme è non vuoto infatti

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

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

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

a − n b = a + a b = a ( 1 + b ) {\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

r = a − q b {\displaystyle r=a-qb}

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

r ′ = r − | b | ≥ 0 {\displaystyle r'=r-|b|\geq 0}

e che

r ′ = r − | b | = ( a − q b ) − | b | = a − ( q + | b | b ) b {\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 ( q , r ) {\displaystyle (q,r)} e ( q ′ , r ′ ) {\displaystyle (q',r')} tali che:

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

allora si ha

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

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

r − r ′ ≤ r < | b | {\displaystyle r-r'\leq r<|b|}
r ′ − r ≤ r ′ < | b | {\displaystyle r'-r\leq r'<|b|}

quindi da (*) si ricava

| q − q ′ | ⋅ | b | ≤ | r − r ′ | < | b | {\displaystyle |q-q'|\cdot |b|\leq |r-r'|<|b|}

ovvero

| q − q ′ | < 1 {\displaystyle |q-q'|<1}

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

| q − q ′ | = 0 {\displaystyle |q-q'|=0}

e quindi, da (*) si deduce anche

r − r ′ = 0 {\displaystyle r-r'=0}

cioè le coppie sono uguali.

Generalizzazioni

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.

Aritmetica modulare

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 Z {\displaystyle \mathbb {Z} } ,

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

rispetto a tale relazione di equivalenza formano un anello.

Divisione intera

A volte con divisione intera viene indicata l'operazione (indicata con il segno ∖ {\displaystyle \setminus } ) definita dalla seguente relazione a ∖ b = ⌊ a / b ⌋ {\displaystyle a\setminus b=\lfloor a/b\rfloor } . La notazione ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } indica la funzione parte intera di x {\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]

Note

  1. ^ Weisstein, Eric W., "Integer Division." From MathWorld--A Wolfram Web Resource, su mathworld.wolfram.com. URL consultato il 16 ottobre 2012.
  2. ^ (EN) (EN) Saman Amarasinghe, Walter Lee, Ben Greenwald, Strength Reduction of Integer Division and Modulo Operations, in Languages and compilers for parallel computing : 14th international workshop, LCPC 2001 : Cuumberland Falls, KY, USA, August 2001 : revised papers / Henry G. Dietz (ed.), Berlin, Heidelberg, Springer-Verlag, 2003, pp. 254-273, ISBN 3-540-04029-3.

Voci correlate

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

Altri progetti

Altri progetti

  • Wikimedia Commons
  • Collabora a Wikimedia Commons Wikimedia Commons contiene immagini o altri file sulla divisione euclidea

Collegamenti esterni

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