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
Définition (cas des entiers naturels)
Soient \( a \) et \( b \) deux entiers naturels avec \( b \neq 0 \). Effectuer la division euclidienne de \( a \) par \( b \) consiste à déterminer deux entiers naturels \( q \) et \( r \) vérifiant les deux conditions suivantes :
a = bq + r \quad \text{et} \quad 0 \leq r < b \]
- \( a \) est appelé le dividende
- \( b \) est appelé le diviseur
- \( q \) est appelé le quotient (ou quotient euclidien)
- \( r \) est appelé le reste
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
Théorème (existence et unicité)
Pour tout couple d’entiers naturels \( (a, b) \) avec \( b \neq 0 \), il existe un unique couple d’entiers naturels \( (q, r) \) tel que :
a = bq + r \quad \text{avec} \quad 0 \leq r < b \]
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 :
E = \{ a – mb \mid m \in \mathbb{N} \text{ et } a – mb \geq 0 \}
\]
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 :
\begin{align*}
a &= bq_1 + r_1 \quad \text{avec} \quad 0 \leq r_1 < b \\ a &= bq_2 + r_2 \quad \text{avec} \quad 0 \leq r_2 < b \end{align*} \]
Par soustraction, nous obtenons :
0 = b(q_1 – q_2) + (r_1 – r_2)
\]
D’où :
r_1 – r_2 = b(q_2 – q_1)
\]
Cela signifie que \( b \) divise \( r_1 – r_2 \). Or, nous avons \( 0 \leq r_1 < b \) et \( 0 \leq r_2 < b \), donc :
-b < r_1 - r_2 < b \]
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.
Théorème (division euclidienne dans les entiers relatifs)
Pour tout entier relatif \( a \in \mathbb{Z} \) et tout entier relatif non nul \( b \in \mathbb{Z}^* \), il existe un unique couple \( (q, r) \) avec \( q \in \mathbb{Z} \) et \( r \in \mathbb{N} \) tel que :
a = bq + r \quad \text{avec} \quad 0 \leq r < |b| \]
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 :
-17 = -5 \times 3 – 2 = -5 \times 3 – 5 + 5 – 2 = 5 \times (-4) + 3
\]
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
Propriété 1 : Caractérisation de la divisibilité
Soient \( a \) et \( b \) deux entiers naturels avec \( b \neq 0 \). Alors \( b \) divise \( a \) (noté \( b \mid a \)) si et seulement si le reste de la division euclidienne de \( a \) par \( b \) est nul.
b \mid a \iff r = 0
\]
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 \).
Propriété 2 : Nombre de restes possibles
Pour un diviseur \( b \) donné, les restes possibles d’une division euclidienne par \( b \) sont exactement les entiers \( 0, 1, 2, \ldots, b-1 \). Il y a donc exactement \( b \) restes possibles.
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 \).
Propriété 3 : Conservation du PGCD
Soient \( a \) et \( b \) deux entiers naturels non nuls, et soit \( r \) le reste de la division euclidienne de \( a \) par \( b \). Alors :
\text{PGCD}(a, b) = \text{PGCD}(b, r)
\]
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 \) :
- On effectue la division euclidienne de \( a \) par \( b \) : \( a = bq_1 + r_1 \) avec \( 0 \leq r_1 < b \)
- Si \( r_1 = 0 \), alors \( \text{PGCD}(a, b) = b \)
- Sinon, on recommence avec le couple \( (b, r_1) \) : \( b = r_1 q_2 + r_2 \)
- On continue ainsi jusqu’à obtenir un reste nul
- 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.
| Étape | Division euclidienne | Calcul |
|---|---|---|
| 1 | \( 252 = 105 \times 2 + 42 \) | \( 105 \times 2 = 210 \), reste \( 42 \) |
| 2 | \( 105 = 42 \times 2 + 21 \) | \( 42 \times 2 = 84 \), reste \( 21 \) |
| 3 | \( 42 = 21 \times 2 + 0 \) | \( 21 \times 2 = 42 \), reste \( 0 \) |
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
Quelle est la différence entre division euclidienne et division décimale ?
La division euclidienne ne s’applique qu’aux nombres entiers et produit deux résultats : un quotient entier et un reste entier strictement inférieur au diviseur. Par exemple, la division euclidienne de 17 par 5 donne un quotient de 3 et un reste de 2. La division décimale, en revanche, peut traiter des nombres décimaux et donne un résultat unique qui peut comporter des décimales, comme 17 divisé par 5 égale 3,4.
Comment effectuer une division euclidienne avec des nombres négatifs ?
Pour la division euclidienne d’un nombre négatif, le reste doit toujours rester positif ou nul. Par exemple, pour diviser moins 17 par 5, on cherche le quotient et le reste tels que moins 17 égale 5 fois le quotient plus le reste, avec le reste compris entre 0 et 4. Le résultat est : moins 17 égale 5 fois moins 4 plus 3, soit un quotient de moins 4 et un reste de 3. Le reste demeure positif même si le dividende est négatif.
Quel est le lien entre division euclidienne et PGCD ?
La division euclidienne est à la base de l’algorithme d’Euclide, qui permet de calculer efficacement le PGCD de deux nombres. Le principe repose sur la propriété suivante : le PGCD de deux nombres a et b est égal au PGCD de b et du reste de la division euclidienne de a par b. En répétant cette opération jusqu’à obtenir un reste nul, le dernier reste non nul obtenu est le PGCD recherché. Cette méthode est beaucoup plus rapide que la décomposition en facteurs premiers.
Peut-on diviser par zéro dans une division euclidienne ?
Non, la division par zéro est impossible en division euclidienne, tout comme dans toute forme de division. Le diviseur doit être un entier non nul. Si on permettait la division par zéro, on rencontrerait des contradictions mathématiques : par exemple, si on pouvait écrire a égale 0 fois q plus r, alors a devrait égaler r pour tout quotient q, ce qui ne permet pas de définir un quotient unique.
Comment poser une division euclidienne ?
Pour poser une division euclidienne, on utilise la méthode de la division posée enseignée à l’école primaire. On prend les chiffres du dividende de gauche à droite, on cherche combien de fois le diviseur est contenu dans le nombre formé, on écrit ce chiffre au quotient, on multiplie par le diviseur, on soustrait, et on abaisse le chiffre suivant. On répète jusqu’à avoir utilisé tous les chiffres. Le nombre obtenu au quotient est le quotient euclidien, et ce qui reste après la dernière soustraction est le reste.