Division euclidienne : énoncé (MPSI)
Division euclidienne
Soient $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$. Il existe un unique couple $(q, r) \in \mathbb{Z} \times \mathbb{N}$ tel que $$a = bq + r \quad \text{et} \quad 0 \leqslant r < b.$$ L'entier $q$ est le quotient, $r$ est le reste de la division euclidienne de $a$ par $b$. On a $q = \left\lfloor \dfrac{a}{b} \right\rfloor$.
Démonstration : Division euclidienne
Existence et unicité
Existence. Posons $q = \lfloor a/b \rfloor$. Par définition de la partie entière, $q \leqslant \dfrac{a}{b} < q + 1$. Comme $b > 0$, on multiplie par $b$ : $bq \leqslant a < bq + b$. Posons $r = a - bq$. Alors $r \in \mathbb{Z}$ et $0 \leqslant r < b$.
Unicité. Supposons $a = bq + r = bq' + r'$ avec $0 \leqslant r, r' < b$. Alors $b(q - q') = r' - r$, et $-b < r' - r < b$. Donc $b|q - q'| < b$, puis $|q - q'| < 1$. Comme $q - q'$ est un entier, $q = q'$, puis $r = r'$.
Avec un dividende négatif
- Division de $47$ par $5$ : $47 = 5 \times 9 + 2$, donc $q = 9$, $r = 2$.
- Division de $-17$ par $5$ : $-17/5 = -3{,}4$, donc $q = \lfloor -3{,}4 \rfloor = -4$ et $r = -17 - 5 \times (-4) = 3$. On écrit $-17 = 5 \times (-4) + 3$.
L'écriture $-17 = 5 \times (-3) - 2$ est exacte mais n'est pas la division euclidienne : le reste doit être positif ou nul.
S’entraîner
- Divisions euclidiennes avec un dividende négatif
- Restes de puissances et divisibilité par congruences
- PGCD de deux nombres de la forme $2^k - 1$
- Un principe de chiffrement à clé publique (type CCINP)