L'objectif de la division euclidienne est de partager une quantité $a$ par $b$ de manière équitable, en trouvant combien de fois $b$ est contenu dans $a$ et ce qui reste après ce partage. Cela est utile, par exemple, pour répartir 17 pommes entre 5 personnes, où chaque personne reçoit 3 pommes et 2 restent.

Soient $a$ et $b$ deux entiers avec $b > 0$.
La division euclidienne de $a$ par $b$ consiste à trouver deux entiers, le quotient $q$ et le reste $r$, tels que:

où

• Dividende $a$ : Le nombre à diviser.

• Diviseur $b$ : Le nombre par lequel on divise.

• Quotient $q$ : Indique combien de fois $b$ peut être soustrait de $a$ sans que le résultat devienne négatif.

• Reste $r$ : La partie de $a$ qui reste après avoir extrait $bq$ de $a$.

Exemple

Considérons la division euclidienne de 17 par 5.

Pour $a = 17$ et $b = 5$, on calcule que $5 \times 3 = 15$ est le plus grand multiple de 5 inférieur à 17, d'où $q = 3$ et $r = 17 - 15 = 2$.

Donc, $17 = 5 \times 3 + 2$. Le quotient est 3 et le reste est 2.

La division euclidienne est la base de l'arithmétique et a de nombreuses applications notamment :

1. Congruences : Les congruences utilisent le reste pour classifier les nombres selon leurs propriétés de divisibilité modulo $b$, essentiel pour les problèmes en théorie des nombres et la cryptographie.

2. Algorithme d'Euclide : Cet algorithme repose sur des divisions euclidiennes successives pour déterminer le plus grand commun diviseur de deux nombres, en répétant le processus jusqu'à obtenir un reste nul.