Division euclidienne, diviseurs et multiples

La division euclidienne d'un entier naturel a par un entier naturel b non nul donne deux entiers, le quotient q et le reste r, tels que a = b × q + r avec 0 ≤ r < b. C'est la division « avec reste » de l'école primaire, et c'est la base de toute l'arithmétique modulaire : conversions de base, PGCD, congruences, chiffrement. Ce chapitre la définit, montre comment la calculer à la main, à la calculatrice et en Python, puis introduit les diviseurs, les multiples et les critères de divisibilité.

Définition

Les deux conditions comptent autant l'une que l'autre. L'égalité seule ne suffit pas : 47 = 5 × 8 + 7 est une égalité juste, mais ce n'est pas la division euclidienne de 47 par 5, car le reste 7 n'est pas inférieur à 5. La division euclidienne de 47 par 5 est 47 = 5 × 9 + 2. En revanche, 47 = 8 × 5 + 7 est bien la division euclidienne de 47 par 8 : le reste 7 est inférieur à 8.

Pourquoi le couple existe-t-il, et pourquoi est-il unique ? Le quotient q est le plus grand entier tel que b × q ≤ a : on retire b de a autant de fois que possible, et ce qui reste est forcément plus petit que b. Si on retirait b une fois de moins, le reste serait au moins égal à b ; une fois de plus, il serait négatif. Il n'y a donc qu'un seul choix possible.

Le programme du BTS se limite aux entiers naturels pour la division euclidienne : tu n'as pas à traiter le cas d'un dividende négatif.

Calculer quotient et reste

À la main, tu poses la division comme à l'école. Pour 2 026 divisé par 7 : 7 × 289 = 2 023, et 2 026 − 2 023 = 3.

2 026 = 7 × 289 + 3, avec 0 ≤ 3 < 7.

À la calculatrice, une division ordinaire donne un nombre décimal : 2 026 ÷ 7 ≈ 289,428 6.

1. Le quotient est la partie entière : q = 289.
2. Le reste se calcule : r = a − b × q = 2 026 − 7 × 289 = 2 026 − 2 023 = 3.

Beaucoup de calculatrices de lycée ont une fonction de division euclidienne (souvent notée ÷R ou « Int÷ » et « Rmdr », selon les modèles). Utilise-la en mode examen si tu la connais, mais sache toujours refaire le calcul avec la partie entière.

En Python, deux opérateurs donnent le quotient et le reste :

2026 // 7        # 289 : quotient (division entière)
2026 % 7         # 3   : reste (modulo)
divmod(2026, 7)  # (289, 3) : les deux à la fois

En pseudo-code, les mêmes opérations s'écrivent DIV et MOD : le cours d'algorithmique les présente avec les opérateurs numériques.

L'opérateur % se lit « modulo ». Il existe dans presque tous les langages (% en C, Java, C#, JavaScript, PHP ; MOD en SQL et dans les tableurs). C'est l'opérateur que tu utiliseras le plus souvent en arithmétique modulaire.

Le reste, un outil de tous les jours

La division euclidienne répond à toutes les questions de la forme « combien de groupes complets, et combien d'éléments restent ».

Convertir une durée. Un script de sauvegarde a duré 10 000 secondes. Combien d'heures, de minutes et de secondes ?

• 10 000 = 3 600 × 2 + 2 800 : 2 heures, il reste 2 800 secondes ;
• 2 800 = 60 × 46 + 40 : 46 minutes, il reste 40 secondes.

La sauvegarde a duré 2 h 46 min 40 s.

Paginer des résultats. Une application affiche 1 234 résultats, 20 par page. 1 234 = 20 × 61 + 14 : il y a 61 pages pleines, plus une page de 14 résultats, soit 62 pages. Le résultat numéro 457 est sur la page (457 − 1) // 20 + 1 = 22 + 1 = 23, en position (457 − 1) % 20 + 1 = 16 + 1 = 17. On retire 1 au départ parce que les numéros commencent à 1 et non à 0.

Trouver un jour de la semaine. Le 29 octobre 2026 est un jeudi. Quel jour serons-nous 100 jours plus tard ? 100 = 7 × 14 + 2 : 14 semaines complètes ramènent au jeudi, puis 2 jours de plus. Ce sera un samedi (le 6 février 2027).

Savoir si un nombre est pair. n est pair si et seulement si le reste de sa division par 2 vaut 0. En Python : n % 2 == 0. C'est aussi le bit de poids faible de son écriture binaire (chapitre 1).

Convertir dans une base. Les divisions successives du chapitre 2 sont des divisions euclidiennes par la base : les restes donnent les chiffres.

Diviseurs et multiples

On dit que b divise a, ou que a est un multiple de b, s'il existe un entier k tel que a = b × k. On note b | a (« b divise a »).

Avec la division euclidienne : b (non nul) divise a si et seulement si le reste de la division de a par b est nul. En Python : a % b == 0.

• 7 divise 2 023, car 2 023 = 7 × 289. En revanche 7 ne divise pas 2 026 (reste 3).
• Les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12.
• Les multiples de 12 sont 0, 12, 24, 36… Tout entier divise 0, et 0 est multiple de tout entier.
• 1 divise tous les entiers, et tout entier non nul est divisible par lui-même.

Pour trouver tous les diviseurs d'un entier n, tu testes les entiers de 1 à √n : chaque diviseur d trouvé en donne un second, n ÷ d. Pour 36 : 1 et 36, 2 et 18, 3 et 12, 4 et 9, 6 et 6. Les diviseurs de 36 sont 1, 2, 3, 4, 6, 9, 12, 18, 36. Le chapitre 6 donne une méthode plus rapide, par la décomposition en facteurs premiers.

Trois propriétés servent souvent dans les démonstrations :

• si d divise a et b, alors d divise a + b, a − b et plus généralement u × a + v × b pour tous entiers u et v ;
• si d divise a et a divise b, alors d divise b (transitivité) ;
• si a = b × q + r, alors tout diviseur commun de a et b divise aussi r. C'est le cœur de l'algorithme d'Euclide.

Les critères de divisibilité

Pour savoir si un entier écrit en base 10 est divisible par un petit nombre, sans poser la division :

Ces critères s'expliquent avec les congruences du chapitre 8 : par exemple, 10 laisse un reste de 1 dans la division par 9, donc chaque chiffre « compte pour lui-même ».

En binaire, les critères les plus utiles concernent les puissances de 2 : un nombre est divisible par 2ᵏ si et seulement si ses k derniers bits sont nuls. (11001000)₂ = 200 se termine par trois 0 : il est divisible par 8. C'est pourquoi un réseau /27, dont les blocs font 32 adresses, commence toujours à une adresse dont les 5 derniers bits valent 0.

Exercices