Divisione euclidea

Da Wikipedia, l'enciclopedia libera.

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 divisore e ogni dividendo 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[modifica | modifica sorgente]

  • 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.

Dimostrazione[modifica | modifica sorgente]

Dimostrazione dell'esistenza.

Consideriamo l'insieme:

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

Tale insieme è non vuoto infatti se n = a si ha

a-nb=a-ab=a(1-b)

se n = −a si ha

a-nb=a+ab=a(1+b)

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

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

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| \geq 0

e che

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) e (q',r') tali che:

a=bq+r, \qquad 0\leq r <|b|
a=bq'+r',\qquad 0\leq r' <|b|

allora si ha

(*) r-r'=-(q-q')b

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

r-r'\leq r < |b|
r'-r\leq r' < |b|

quindi da (*) si ricava

|q-q'|\cdot |b| \leq |r-r'|<|b|

ovvero

|q-q'|<1

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

|q-q'|=0

e quindi, da (*) si deduce anche

r-r'=0

cioè le coppie sono uguali.

Generalizzazioni[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi 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 \mathbb Z,

 [0],[1], ... , [n-2], [n-1]

rispetto a tale relazione di equivalenza formano un anello.

Divisione intera[modifica | modifica sorgente]

bussola Disambiguazione – Se stai cercando divisione intera nel campo dell'informatica, vedi divisione intera (informatica).

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

Questa operazione viene talvolta indicata nei software di calcolo anche come div. In realtà 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[modifica | modifica sorgente]

  1. ^ Weisstein, Eric W., "Integer Division." From MathWorld--A Wolfram Web Resource. 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[modifica | modifica sorgente]

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