Prezzi Registrazione Login
Qui si risolve LOGO
a

Menu

M

Chiudi

La divisione euclidea

Insiemi numerici N, Z, Q, R

Home » La divisione euclidea

 
 

Autori e revisori

Leggi...

Autori: .

Revisori: .


 
 

Notazioni

Leggi...

\mathbb{N}    Insieme dei numeri naturali: 0,1,2,\dots;
\mathbb{Z}    Insieme dei numeri interi relativi: \dots,-2,-1,0,1,2,\dots.


 
 

Introduzione

Leggi...

La divisione euclidea tra numeri interi è la formalizzazione dell’operazione di divisione con resto che tutti abbiamo imparato durante la scuola elementare tra numeri interi positivi: dato un dividendo a e un divisore b, è possibile determinare un quoziente q e un resto, compreso tra 0 e b-1, tali che a=b \cdot q + r. Il quoziente q ci dice qual è il massimo multiplo intero di b che sia anche minore di a e il resto r ci dice quale sia appunto la differenza tra tale multiplo e a.

In questo articolo analizziamo nel dettaglio questo concetto nell’insieme \mathbb{Z} dei numeri interi relativi e ne forniamo le proprietà fondamentali.


 
 

La divisione euclidea

Teorema 1. Siano a,\,b\,\in\mathbb{Z} con b\neq 0 allora esistono e sono unici q,\,r\,\in\mathbb{N} tale che

\begin{equation*} a=b\cdot q+r\qquad 0\leq r<|b| \end{equation*}

dove q è detto quoziente e r resto della divisione euclidea.

\[\quad\]

Dimostrazione. Dimostriamo l’esistenza del quoziente e del resto per la divisione euclidea in \mathbb{Z} e trattiamo i casi a\geq 0 e a<0 separatamente.

Supponiamo a\geq 0 e applichiamo il principio di induzione forte rispetto ad a.

\[\quad\]

  • Se a=0 allora basta porre q=r=0 quindi P(0) è verificata

    •  

  • Supponiamo vera l’ipotesi P per ogni 0\leq k\leq a e dimostriamo l’asserto per a.

    – Se |b|>a poniamo q=0 e r=a

    – Se |b|\leq a consideriamo k=a-|b| allora per l’ipotesi induttiva esistono due numeri interi q' e r' tale che

    \begin{equation*} a-|b|=q'b+r'\qquad 0\leq r'<|b| \end{equation*}

    Allora

    \begin{equation*} a=|b|+q'b+r'\qquad 0\leq r'<|b| \end{equation*}

    Se b>0 basterà scegliere q=q'+1 e se b<0 q=q'-1; in entrambi i casi P(a) è verificata. Per il principio di induzione la proprietà è vera per ogni a

Per a<0 basterà sfruttare il risultato appena ottenuto per -a e scegliere opportunamente q e r in \mathbb{Z}.

Per l’unicità supponiamo per assurdo che esistano q,\,r\in\mathbb{Z} e q',\,r'\in\mathbb{Z} tale che

\begin{equation*} \begin{split} &a=b\cdot q+r\qquad 0\leq r<|b|\\ &a=b\cdot q'+r'\qquad 0\leq r'<|b| \end{split} \end{equation*}

Supponiamo r'\leq r allora (ripercorrendo l’analogo ragionamento per la divisione euclidea in \mathbb{N})

\begin{equation*} 0\leq r-r'=b(q'-q) \end{equation*}

Passando ai valori assoluti

\begin{equation*} |b(q'-q)|=|b||q'-q|=r-r'\leq r<|b| \end{equation*}

Quindi |q'-q|=0\Rightarrow q'=q e r'=r.

Definizione 2. Dati a,\,b\,\in\mathbb{Z} diremo che b divide a e scrivereme b|a se esiste un elemento q\in\mathbb{Z} tale che a=bq.

\[\quad\]

Osservazione 3. Possiamo affermare equivalentemente che b|a se il resto della divisione euclidea è nullo.

Definizione 4. Siano a,\,b\in\mathbb{Z}. Un elemento d\in\mathbb{Z} si dice {massimo comune divisore tra a e b se

\[\quad\]

  1. d|a e d|b

    2.  

  2. Per ogni intero d' tale che d'|a e d'|b, si ha che d'|d.

Come è noto, scriveremo d=MCD(a,b).

\[\quad\]

L’esistenza del massimo comune divisore è garantita dal teorema 5, mentre l’unicità è garantita solo nel caso in cui venga scelto un segno privilegiato; infatti se d=MCD(a,b) anche -d soddisferà le ipotesi di massimo comune divisore. Il generale quando si parla di massimo comune divisore in \mathbb{Z}, si intende il massimo comune divisore positivo.

Definizione 5. Due elementi a,\,b\in\mathbb{Z} tale che d=MCD(a,b)=1 si dicono coprimi.