Division euclidienne : définition, preuve et exemples

La division euclidienne constitue l'un des fondements de l'arithmétique élémentaire. Présente dès l'école primaire sous forme d'opération pratique, elle trouve sa rigueur mathématique dans un théorème d'existence et d'unicité qui garantit que toute division d'un entier par un autre produit toujours un quotient et un reste bien définis. Cette opération, dont le nom rend hommage au mathématicien grec Euclide (vers 300 av. J.-C.), auteur des célèbres Éléments, dépasse largement le cadre du calcul élémentaire pour devenir un outil indispensable en arithmétique modulaire, dans le calcul du PGCD via l'algorithme d'Euclide, ou encore dans l'étude des anneaux euclidiens.

Comprendre la division euclidienne, c'est saisir comment un nombre entier peut être décomposé relativement à un autre, révélant ainsi une structure profonde des nombres qui éclaire de nombreux résultats en théorie des nombres.

Définition de la division euclidienne

La condition essentielle $0 \leq r < b$ signifie que le reste doit être strictement inférieur au diviseur. C'est cette contrainte qui garantit l'unicité du quotient et du reste. Sans elle, une infinité de décompositions seraient possibles. Par exemple, on pourrait écrire $17 = 3 \times 5 + 2$ mais aussi $17 = 3 \times 4 + 5$, or seule la première égalité respecte la condition sur le reste.

Intuitivement, la division euclidienne répond à la question : combien de fois peut-on soustraire le diviseur $b$ du dividende $a$ avant d'obtenir un nombre plus petit que $b$ ? Le nombre de soustractions effectuées est le quotient $q$, et ce qui reste est le reste $r$.

Le théorème de la division euclidienne

Ce théorème comporte deux affirmations cruciales :

• Existence : pour tout dividende et tout diviseur non nul, il est toujours possible de trouver un quotient et un reste satisfaisant les conditions
• Unicité : ces quotient et reste sont uniques, c'est-à-dire qu'il n'existe qu'une seule manière de décomposer $a$ sous la forme $bq + r$ avec $r$ compris entre 0 et $b-1$

Cette double garantie fait de la division euclidienne une opération parfaitement définie, à l'inverse d'opérations partielles ou ambiguës.

Interprétation géométrique et intuitive

La division euclidienne possède plusieurs interprétations concrètes qui éclairent sa nature :

Interprétation par partage équitable

Imaginons que nous devions répartir 47 billes entre 5 enfants de manière équitable. Chaque enfant recevra le même nombre de billes, et il restera éventuellement des billes impossibles à distribuer sans léser quelqu'un. La division euclidienne de 47 par 5 donne $47 = 5 \times 9 + 2$. Chaque enfant reçoit donc 9 billes (le quotient), et il reste 2 billes (le reste) qui ne peuvent être distribuées équitablement.

Interprétation sur la droite numérique

Sur une droite graduée, la division euclidienne de $a$ par $b$ revient à trouver le plus grand multiple de $b$ qui ne dépasse pas $a$. Ce multiple est $bq$, et la distance entre $bq$ et $a$ est précisément le reste $r$. Autrement dit, le quotient $q$ compte combien de "sauts" de longueur $b$ on peut effectuer depuis l'origine sans dépasser $a$.

Exemple détaillé

Effectuons la division euclidienne de 89 par 12.

Nous cherchons le plus grand multiple de 12 qui ne dépasse pas 89 :

• $12 \times 7 = 84$ (inférieur à 89)
• $12 \times 8 = 96$ (supérieur à 89)

Le quotient est donc $q = 7$. Le reste se calcule par $r = 89 - 84 = 5$.

Nous obtenons : $89 = 12 \times 7 + 5$ avec $0 \leq 5 < 12$. La condition sur le reste est bien vérifiée.

Démonstration du théorème

Nous allons démontrer successivement l'existence puis l'unicité du couple $(q, r)$.

Démonstration de l’existence

Soit $a \in \mathbb{N}$ et $b \in \mathbb{N}^*$. Nous devons montrer qu'il existe $q$ et $r$ dans $\mathbb{N}$ tels que $a = bq + r$ avec $0 \leq r < b$.

Cas 1 : Si $a < b$

Dans ce cas, il suffit de poser $q = 0$ et $r = a$. On a bien $a = b \times 0 + a$ et $0 \leq a < b$ puisque $a < b$ par hypothèse.

Cas 2 : Si $a \geq b$

Considérons l'ensemble $E$ défini par :

Cet ensemble contient tous les entiers naturels de la forme $a - mb$ où $m$ est un entier naturel. L'ensemble $E$ est non vide car il contient $a$ (obtenu pour $m = 0$). De plus, $E$ est une partie non vide de $\mathbb{N}$, donc elle admet un plus petit élément par la propriété de bon ordre des entiers naturels. Notons $r$ ce plus petit élément.

Il existe donc $q \in \mathbb{N}$ tel que $r = a - qb$, c'est-à-dire $a = bq + r$.

Montrons que $r < b$. Supposons par l'absurde que $r \geq b$. Alors $a - (q+1)b = a - qb - b = r - b \geq 0$, donc $a - (q+1)b \in E$. Or $a - (q+1)b = r - b < r$, ce qui contredit la minimalité de $r$ dans $E$. Donc nécessairement $r < b$.

Nous avons ainsi construit un couple $(q, r)$ vérifiant les conditions requises.

Démonstration de l’unicité

Supposons qu'il existe deux couples $(q_1, r_1)$ et $(q_2, r_2)$ vérifiant les conditions de la division euclidienne :

Par soustraction, nous obtenons :

D'où :

Cela signifie que $b$ divise $r_1 - r_2$. Or, nous avons $0 \leq r_1 < b$ et $0 \leq r_2 < b$, donc :

Le seul multiple de $b$ strictement compris entre $-b$ et $b$ est 0. Donc $r_1 - r_2 = 0$, c'est-à-dire $r_1 = r_2$.

En reportant dans l'égalité $b(q_1 - q_2) = 0$ et sachant que $b \neq 0$, nous obtenons $q_1 = q_2$.

L'unicité est donc établie.

Extension aux entiers relatifs

La division euclidienne se généralise aux entiers relatifs, c'est-à-dire lorsque le dividende $a$ peut être négatif ou lorsque le diviseur $b$ est négatif.

Notez que le reste $r$ demeure toujours un entier naturel (positif ou nul), tandis que le quotient $q$ peut être négatif. La condition porte sur la valeur absolue du diviseur : $0 \leq r < |b|$.

Exemples avec entiers négatifs

Exemple 1 : Division euclidienne de $-17$ par $5$

Nous cherchons $q$ et $r$ tels que $-17 = 5q + r$ avec $0 \leq r < 5$.

Si l'on effectue la division de $17$ par $5$, on obtient $17 = 5 \times 3 + 2$. Donc $-17 = -5 \times 3 - 2$.

Mais le reste $-2$ ne vérifie pas la condition $0 \leq r < 5$. Réécrivons :

Donc $q = -4$ et $r = 3$, avec bien $0 \leq 3 < 5$.

Exemple 2 : Division euclidienne de $17$ par $-5$

Nous cherchons $q$ et $r$ tels que $17 = -5q + r$ avec $0 \leq r < |-5| = 5$.

Réécrivons : $17 = -5 \times (-3) + 2$. Vérifions : $-5 \times (-3) = 15$, et $15 + 2 = 17$. De plus, $0 \leq 2 < 5$.

Donc $q = -3$ et $r = 2$.

Ces exemples illustrent que le reste est toujours positif ou nul, même lorsque le dividende ou le diviseur est négatif. C'est cette convention qui garantit l'unicité de la division euclidienne dans $\mathbb{Z}$.

Propriétés fondamentales

Lorsque le reste est nul, on dit que la division est exacte et que $a$ est un multiple de $b$, ou que $b$ est un diviseur de $a$.

Cette propriété est à la base de l'arithmétique modulaire, où l'on classe les entiers selon leur reste dans la division par $n$.

Cette propriété est fondamentale car elle permet de calculer le PGCD de deux nombres par une suite de divisions euclidiennes successives, méthode connue sous le nom d'algorithme d'Euclide.

Applications : l’algorithme d’Euclide

L'une des applications les plus importantes de la division euclidienne est le calcul du PGCD (Plus Grand Commun Diviseur) de deux entiers via l'algorithme d'Euclide. Cet algorithme, décrit dans les Éléments d'Euclide, repose sur la propriété de conservation du PGCD énoncée précédemment.

Principe de l’algorithme d’Euclide

Pour calculer le PGCD de deux entiers naturels $a$ et $b$ avec $a \geq b > 0$ :

1. On effectue la division euclidienne de $a$ par $b$ : $a = bq_1 + r_1$ avec $0 \leq r_1 < b$
2. Si $r_1 = 0$, alors $\text{PGCD}(a, b) = b$
3. Sinon, on recommence avec le couple $(b, r_1)$ : $b = r_1 q_2 + r_2$
4. On continue ainsi jusqu'à obtenir un reste nul
5. Le dernier reste non nul est le PGCD de $a$ et $b$

Exemple de calcul

Calculons le PGCD de 252 et 105 par l'algorithme d'Euclide.

Le dernier reste non nul est 21. Donc $\text{PGCD}(252, 105) = 21$.

Justification mathématique

Pourquoi cet algorithme fonctionne-t-il ? Reprenons la propriété : si $a = bq + r$, alors $\text{PGCD}(a, b) = \text{PGCD}(b, r)$.

Démontrons-la brièvement. Soit $d$ un diviseur commun de $a$ et $b$. Alors $d \mid a$ et $d \mid b$, donc $d \mid (a - bq)$, c'est-à-dire $d \mid r$. Réciproquement, si $d$ divise $b$ et $r$, alors $d \mid (bq + r)$, donc $d \mid a$. Les diviseurs communs de $a$ et $b$ sont donc exactement les diviseurs communs de $b$ et $r$, et en particulier leur PGCD est le même.

L'algorithme se termine nécessairement car la suite des restes est strictement décroissante : $r_1 > r_2 > r_3 > \ldots \geq 0$. Une suite strictement décroissante d'entiers naturels est nécessairement finie.

Critères de divisibilité

La division euclidienne permet d'établir des critères de divisibilité, c'est-à-dire des règles simples pour déterminer si un nombre est divisible par un autre sans effectuer la division complète.

Divisibilité par 2

Un entier est divisible par 2 si et seulement si son chiffre des unités est 0, 2, 4, 6 ou 8. Autrement dit, un nombre pair est divisible par 2.

Divisibilité par 5

Un entier est divisible par 5 si et seulement si son chiffre des unités est 0 ou 5.

Divisibilité par 10

Un entier est divisible par 10 si et seulement si son chiffre des unités est 0.

Divisibilité par 3

Un entier est divisible par 3 si et seulement si la somme de ses chiffres est divisible par 3. Par exemple, 1 248 est divisible par 3 car $1 + 2 + 4 + 8 = 15$ et 15 est divisible par 3.

Divisibilité par 9

Un entier est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9.

Ces critères découlent de propriétés de congruence et permettent des vérifications rapides sans calculatrice.

Conclusion et synthèse

La division euclidienne est bien plus qu'une simple opération arithmétique : c'est un théorème fondamental qui garantit que tout entier peut être décomposé de manière unique relativement à un diviseur. Cette décomposition unique en quotient et reste structure l'arithmétique des entiers et ouvre la voie à de nombreux outils puissants comme l'algorithme d'Euclide pour le calcul du PGCD, l'arithmétique modulaire avec les classes de congruence, ou encore l'extension aux polynômes dans la théorie des anneaux euclidiens.

Maîtriser la division euclidienne, c'est comprendre une pierre angulaire des mathématiques, présente du collège (avec les problèmes de partage équitable) jusqu'aux études supérieures (avec les structures algébriques). Retenez bien les deux conditions essentielles : l'égalité $a = bq + r$ et l'encadrement strict du reste $0 \leq r < b$ ou $0 \leq r < |b|$ pour les entiers relatifs.

Questions fréquentes sur la division euclidienne