C4.1 - Împărțirea euclidiană

---

Cine a fost Euclid?

Euclid a transformat geometria dintr-o colecție de reguli practice într-o știință deductivă riguroasă. El a demonstrat că teoremele complexe pot fi derivate logic dintr-un set minim de adevăruri evidente numite axiome. Deși este faimos pentru geometrie, Euclid a adus contribuții majore în aritmetică

Împărțirea euclidiană

Teorema împărțirii euclidiene

Fie $a$ și $b$ două numere naturale, cu $b$ diferit de $0$. Atunci există o unică pereche de numere naturale $c$ și $r$, astfel încât:

$a = b \cdot c + r, \quad 0 \leq r < b$

Demonstrație

Exemplu:

Împărțirea euclidiană a numărului $85$ cu $11$:

$$85 = 11 \cdot 7 + 8 \text{, unde } 0 \leq 8 < 11$$

8 reprezintă restul împărțirii

7 reprezintă câtul împărțirii.

Observații

1. Împărțirea euclidiană înseamnă să impartim un număr $a$ în $b$ grupe egale. Fiecare grupă vă avea câte $c$ elemente, iar cele $r$ elemente care nu mai pot fi împărțite formează restul.

2. $a$ se numește deimpartitul, $b$ se numește impartitorul, $c$ se numește catul și $r$ se numește restul.

3. Există un algoritm de la care se poate realiza împărțirea euclidiană. Acesta presupune scăderea repetată a lui $b$ din $a$, până când se obține un rest mai mic decât $b$. Numărul de scăderi ne arată catul, iar numărul rămas este restul.

   Exemplu: fie împărțirea euclidiană a numărului $2187$ cu $16$

   Așezăm împărțirea astfel:

   $$\begin{array}{cccc|l} 2 & 1 & 8 & 7 & \begin{array}{c} 16 \\ \hline 136 \end{array} \\ & 5 & 8 & & \\ & 1 & 0 & 7 & \\ & & 1 & 1 & \end{array}$$

   Citim atunci:

   $$2187 = 16 \cdot 136 + 11$$

4. Dacă $a < b$, atunci $a = b \cdot 0 + a$. Altfel spus, câtul este $0$, iar restul este $a$.

5. Dacă $a = b$, atunci $a = a \cdot 1 + 0$. Altfel spus, câtul este $1$, iar restul este $0$.

6. Condiția $0 \leq r < b$ este necesară. Într-adevăr, egalitatea $a = b \cdot c + r$ singură nu ne lasă întotdeauna să deosebim împărțitorul de cât.

   Exemplu: să luăm egalitatea $32 = 6 \cdot 5 + 2$

   Restul $2$ fiind strict mai mic și decât $6$, și decât $5$, ne este imposibil să stabilim cu precizie care este câtul și care este împărțitorul acestei împărțiri euclidiene.