I. La relation de divisibilité
L'arithmétique est l'étude des propriétés des nombres entiers. La notion centrale est celle de divisibilité : quand peut-on partager un entier en parts égales sans reste ?
Soient \(a\) et \(b\) deux entiers avec \(b \neq 0\). On dit que \(b\) divise \(a\), et on écrit \(b \mid a\), s'il existe un entier \(k\) tel que : \[a = k \times b\] On dit aussi que \(a\) est un multiple de \(b\), ou que \(b\) est un diviseur de \(a\).
.png)
La relation de divisibilité vérifie trois propriétés essentielles :
- Réflexivité : \(a \mid a\) pour tout entier \(a \neq 0\).
- Transitivité : si \(a \mid b\) et \(b \mid c\), alors \(a \mid c\).
- Linéarité : si \(a \mid b\) et \(a \mid c\), alors \(a \mid (ub + vc)\) pour tous entiers \(u, v\). En particulier \(a \mid (b+c)\) et \(a \mid (b-c)\).
Supposons \(a \mid b\) et \(b \mid c\). Alors :
Il existe \(k_1\) tel que \(b = k_1 a\).
Il existe \(k_2\) tel que \(c = k_2 b\).
Donc : \(c = k_2 b = k_2 (k_1 a) = (k_1 k_2) a\).
Comme \(k_1 k_2\) est un entier, on a bien \(a \mid c\). \(\square\)
II. Critères de divisibilité usuels
Plutôt que de diviser explicitement, on peut souvent déterminer la divisibilité par inspection des chiffres du nombre.
| Diviseur | Critère | Exemple |
|---|---|---|
| 2 | Le dernier chiffre est pair (0, 2, 4, 6, 8) | 348 : dernier chiffre 8, pair ✓ |
| 3 | La somme des chiffres est divisible par 3 | 348 : 3+4+8=15, divisible par 3 ✓ |
| 4 | Les deux derniers chiffres forment un nombre divisible par 4 | 348 : 48 ÷ 4 = 12 ✓ |
| 5 | Le dernier chiffre est 0 ou 5 | 345 : dernier chiffre 5 ✓ |
| 9 | La somme des chiffres est divisible par 9 | 729 : 7+2+9=18, divisible par 9 ✓ |
| 10 | Le dernier chiffre est 0 | 2 340 : dernier chiffre 0 ✓ |
Tout entier à trois chiffres s'écrit \(n = 100a + 10b + c\).
\(n = 99a + 9b + (a + b + c)\)
\(= 3(33a + 3b) + (a+b+c)\)
Comme \(3 \mid 3(33a+3b)\), on a \(3 \mid n \iff 3 \mid (a+b+c)\). \(\square\)
Le raisonnement s'étend à tout nombre à \(n\) chiffres car \(10^k - 1\) est toujours divisible par 9 (et donc par 3).
III. La division euclidienne
La division euclidienne est le fondement de l'arithmétique entière. Elle généralise la notion de divisibilité en introduisant le reste.
Pour tout entier \(a\) et tout entier \(b > 0\), il existe un unique couple d'entiers \((q, r)\) tel que :
\[a = bq + r \quad \text{avec} \quad 0 \leq r < b\]\(q\) s'appelle le quotient et \(r\) le reste de la division de \(a\) par \(b\).
En particulier, \(b \mid a \iff r = 0\).
a) Division de 347 par 12 :
\(347 = 12 \times 28 + 11\) donc \(q = 28\), \(r = 11\).
Vérification : \(12 \times 28 = 336\), \(336 + 11 = 347\) ✓ et \(0 \leq 11 < 12\) ✓
b) Division de 720 par 15 :
\(720 = 15 \times 48 + 0\) donc \(r = 0\) : 15 divise 720.
c) Partage de 500 FCFA en billets de 200 FCFA :
\(500 = 200 \times 2 + 100\) : on peut donner 2 billets de 200 FCFA, il reste 100 FCFA.
IV. Le Plus Grand Commun Diviseur (PGCD)
Étant donné deux entiers, on cherche souvent le plus grand entier qui les divise tous les deux — c'est le PGCD.
Le Plus Grand Commun Diviseur de deux entiers \(a\) et \(b\) (non tous deux nuls), noté \(\text{PGCD}(a, b)\) ou \(a \wedge b\), est le plus grand entier qui divise à la fois \(a\) et \(b\).
Si \(\text{PGCD}(a,b) = 1\), on dit que \(a\) et \(b\) sont premiers entre eux (ou coprimes).
Les diviseurs communs de 36 et 48 sont : 1, 2, 3, 6. Le plus grand est PGCD(36, 48) = 6.
V. Algorithme d'Euclide
Lister tous les diviseurs pour trouver le PGCD est fastidieux pour de grands nombres. L'algorithme d'Euclide, vieux de plus de 2 300 ans, permet de calculer le PGCD très efficacement par divisions euclidiennes successives.
Pour tous entiers \(a\) et \(b\) avec \(b > 0\), si \(a = bq + r\), alors :
\[\text{PGCD}(a, b) = \text{PGCD}(b, r)\]Soit \(d = \text{PGCD}(a,b)\). On montre que \(d = \text{PGCD}(b,r)\).
Comme \(d \mid a\) et \(d \mid b\), et \(r = a - bq\), on a \(d \mid r\). Donc \(d\) divise \(b\) et \(r\).
Réciproquement, soit \(d'\) un diviseur commun de \(b\) et \(r\). Alors \(d' \mid bq + r = a\), donc \(d'\) divise \(a\) et \(b\), donc \(d' \leq d\).
Ainsi \(d\) est le plus grand diviseur commun de \(b\) et \(r\) : \(d = \text{PGCD}(b,r)\). \(\square\)
On effectue des divisions euclidiennes successives jusqu'à obtenir un reste nul. Le dernier reste non nul est le PGCD.
- Diviser \(a\) par \(b\) : \(a = bq_1 + r_1\)
- Diviser \(b\) par \(r_1\) : \(b = r_1 q_2 + r_2\)
- Diviser \(r_1\) par \(r_2\) : \(r_1 = r_2 q_3 + r_3\)
- Continuer jusqu'à \(r_n = 0\). Alors \(\text{PGCD}(a,b) = r_{n-1}\).
\(252 = 180 \times 1 + 72\)
\(180 = 72 \times 2 + 36\)
\(72 = 36 \times 2 + 0\) ← reste nul, on s'arrête
Le dernier reste non nul est 36.
\(1\,071 = 462 \times 2 + 147\)
\(462 = 147 \times 3 + 21\)
\(147 = 21 \times 7 + 0\) ← reste nul
VI. Le Plus Petit Commun Multiple (PPCM)
Le Plus Petit Commun Multiple de deux entiers \(a\) et \(b\) (non nuls), noté \(\text{PPCM}(a,b)\) ou \(a \vee b\), est le plus petit entier strictement positif qui est à la fois multiple de \(a\) et multiple de \(b\).
Ce qui donne directement : \(\text{PPCM}(a,b) = \dfrac{a \times b}{\text{PGCD}(a,b)}\)
Si \(a = \prod p_i^{\alpha_i}\) et \(b = \prod p_i^{\beta_i}\), alors :
\(\text{PGCD}(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)}\)
\(\text{PPCM}(a,b) = \prod p_i^{\max(\alpha_i,\beta_i)}\)
Or \(\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta\), donc :
\(\text{PGCD} \times \text{PPCM} = \prod p_i^{\alpha_i+\beta_i} = a \times b \quad \square\)
On a calculé \(\text{PGCD}(36, 48) = 6\) (par liste des diviseurs plus haut).
\(\text{PPCM}(36, 48) = \dfrac{36 \times 48}{6} = \dfrac{1\,728}{6} = 288\)
Vérification : \(288 = 36 \times 8 = 48 \times 6\) ✓
VII. Décomposition en facteurs premiers
Tout entier \(n \geq 2\) peut s'écrire de manière unique comme produit de nombres premiers — c'est le théorème fondamental de l'arithmétique.
Tout entier \(n \geq 2\) se décompose de façon unique (à l'ordre des facteurs près) en produit de nombres premiers : \[n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}\] où les \(p_i\) sont des nombres premiers distincts et les \(\alpha_i \geq 1\).
Décomposons 360 et 504 :
\(360 = 2^3 \times 3^2 \times 5\)
\(504 = 2^3 \times 3^2 \times 7\)
PGCD (prendre les min des exposants) :
\(\text{PGCD}(360, 504) = 2^{\min(3,3)} \times 3^{\min(2,2)} \times 5^{\min(1,0)} \times 7^{\min(0,1)}\)
\(= 2^3 \times 3^2 \times 5^0 \times 7^0 = 8 \times 9 = 72\)
PPCM (prendre les max des exposants) :
\(\text{PPCM}(360, 504) = 2^3 \times 3^2 \times 5 \times 7 = 8 \times 9 \times 5 \times 7 = 2\,520\)
Vérification : \(72 \times 2\,520 = 181\,440 = 360 \times 504\) ✓
VIII. Application burkinabè — Partages équitables
Une coopérative agricole de Bama dispose de 252 kg de riz et 180 kg de sorgho. Elle veut former des lots identiques, chacun contenant le même nombre de kilos de riz et le même nombre de kilos de sorgho, en utilisant toute la quantité disponible. Combien de lots peut-elle former au maximum, et quelle est la composition de chaque lot ?
Le nombre de lots doit diviser à la fois 252 et 180.
Nombre maximal de lots = \(\text{PGCD}(252, 180)\).
Algorithme d'Euclide : \(252 = 180 \times 1 + 72\) ; \(180 = 72 \times 2 + 36\) ; \(72 = 36 \times 2 + 0\)
\(\text{PGCD}(252, 180) = 36\)
Chaque lot contient : \(252 \div 36 = 7\) kg de riz et \(180 \div 36 = 5\) kg de sorgho.
Deux camions desservent le marché de Rood Woko à Ouagadougou. Le premier fait un aller-retour toutes les 36 minutes, le second toutes les 48 minutes. Ils partent ensemble à 6h00. À quelle heure se retrouveront-ils ensemble au marché pour la première fois ?
On cherche le plus petit multiple commun : \(\text{PPCM}(36, 48)\).
\(\text{PGCD}(36, 48)\) : \(48 = 36 \times 1 + 12\) ; \(36 = 12 \times 3 + 0\) → \(\text{PGCD} = 12\)
\(\text{PPCM}(36, 48) = \dfrac{36 \times 48}{12} = \dfrac{1\,728}{12} = 144\) minutes
\(144 \text{ min} = 2\text{h}24\text{min}\) après le départ.
Une ONG humanitaire à Dori distribue des vivres aux familles de la région. Elle dispose de 630 kg de mil, 420 kg de riz et 210 kg d'huile (en décilitres). Elle veut former des colis identiques utilisant exactement toutes les denrées.
- a) Calculer \(\text{PGCD}(630, 420)\) par l'algorithme d'Euclide.
- b) Vérifier que ce PGCD divise aussi 210.
- c) En déduire le nombre maximum de colis identiques et la composition de chacun.
- d) Les camions de livraison partent de Ouagadougou toutes les 45 minutes et de Kaya toutes les 30 minutes. Ils partent simultanément à 7h. Quand repartiront-ils ensemble ? Calculer \(\text{PPCM}(45, 30)\).
✏️ Exercices d'application
Pour chacun des nombres suivants, déterminer par quels entiers (parmi 2, 3, 4, 5, 9) il est divisible, en justifiant par le critère approprié :
- a) \(n = 2\,736\)
- b) \(n = 5\,490\)
- c) \(n = 10\,125\)
b) \(5\,490\) : dernier chiffre 0 → divisible par 2, 5 et 10. Somme : 5+4+9+0=18, divisible par 9 → divisible par 3 et 9. Deux derniers chiffres 90 : 90÷4=22,5 → non divisible par 4.
c) \(10\,125\) : dernier chiffre 5 → divisible par 5. Impair → non divisible par 2. Somme : 1+0+1+2+5=9, divisible par 9 → divisible par 3 et 9. Non divisible par 4 (impair).
Effectuer la division euclidienne et écrire \(a = bq + r\) :
- a) \(a = 847\), \(b = 23\)
- b) \(a = 2\,015\), \(b = 17\)
- c) Un producteur de karité a 1 260 noix à répartir en sachets de 35 noix. Combien de sachets complets peut-il remplir ? Combien de noix restent-elles ?
b) \(2\,015 = 17 \times 118 + 9\). Vérification : \(17 \times 118 = 2\,006\), \(2\,006+9=2\,015\) ✓
c) \(1\,260 = 35 \times 36 + 0\). Il peut remplir exactement 36 sachets, sans reste (35 divise 1 260).
Calculer les PGCD suivants par l'algorithme d'Euclide, en détaillant toutes les étapes :
- a) \(\text{PGCD}(315, 105)\)
- b) \(\text{PGCD}(1\,260, 756)\)
- c) \(\text{PGCD}(2\,023, 899)\)
b) \(1\,260 = 756 \times 1 + 504\) ; \(756 = 504 \times 1 + 252\) ; \(504 = 252 \times 2 + 0\)
\(\text{PGCD}(1\,260, 756) = 252\)
c) \(2\,023 = 899 \times 2 + 225\) ; \(899 = 225 \times 3 + 224\) ; \(225 = 224 \times 1 + 1\) ; \(224 = 1 \times 224 + 0\)
\(\text{PGCD}(2\,023, 899) = 1\) — ces deux entiers sont premiers entre eux.
Trois équipes de construction travaillent sur le barrage de Bagré. L'équipe A fait une pause toutes les 20 minutes, l'équipe B toutes les 30 minutes, l'équipe C toutes les 45 minutes. Elles commencent toutes en même temps.
- a) Calculer \(\text{PGCD}(20, 30)\) puis \(\text{PPCM}(20, 30)\).
- b) Calculer \(\text{PPCM}(20, 30, 45)\). (Indication : \(\text{PPCM}(a,b,c) = \text{PPCM}(\text{PPCM}(a,b),c)\).)
- c) Après combien de minutes les trois équipes feront-elles une pause simultanée pour la première fois ?
\(\text{PPCM}(20,30) = \frac{20 \times 30}{10} = 60\) minutes.
b) \(\text{PPCM}(60, 45)\) : \(\text{PGCD}(60,45)\) → \(60 = 45 \times 1 + 15\) ; \(45 = 15 \times 3 + 0\) → PGCD = 15
\(\text{PPCM}(60,45) = \frac{60 \times 45}{15} = 180\)
Donc \(\text{PPCM}(20,30,45) = 180\) minutes.
c) Les trois équipes font leur première pause simultanée après 180 minutes = 3 heures.
Décomposer en facteurs premiers, puis calculer PGCD et PPCM :
- a) \(a = 360\) et \(b = 450\)
- b) Un rectangle de longueur 360 cm et de largeur 252 cm doit être entièrement recouvert de carreaux carrés identiques sans les couper. Quelle est la plus grande taille possible des carreaux ?
\(\text{PGCD}(360,450) = 2^1 \times 3^2 \times 5^1 = 2 \times 9 \times 5 = 90\)
\(\text{PPCM}(360,450) = 2^3 \times 3^2 \times 5^2 = 8 \times 9 \times 25 = 1\,800\)
Vérification : \(90 \times 1\,800 = 162\,000 = 360 \times 450\) ✓
b) La taille du côté des carreaux doit diviser à la fois 360 et 252.
La plus grande taille est \(\text{PGCD}(360, 252)\).
\(360 = 252 \times 1 + 108\) ; \(252 = 108 \times 2 + 36\) ; \(108 = 36 \times 3 + 0\)
\(\text{PGCD}(360,252) = 36\) cm.
Le nombre de carreaux : \(\frac{360}{36} \times \frac{252}{36} = 10 \times 7 = 70\) carreaux.
Récapitulatif — Divisibilité, PGCD, PPCM
- Divisibilité : \(b \mid a\) s'il existe \(k\) entier tel que \(a = kb\). Propriétés : réflexivité, transitivité, linéarité.
- Division euclidienne : \(a = bq + r\) avec \(0 \leq r < b\), unique. \(b \mid a \iff r = 0\).
- PGCD : plus grand entier divisant à la fois \(a\) et \(b\). Se calcule par l'algorithme d'Euclide : divisions successives jusqu'au reste nul.
- Algorithme d'Euclide : \(\text{PGCD}(a,b) = \text{PGCD}(b, r)\) où \(r\) est le reste de \(a \div b\).
- PPCM : plus petit multiple commun positif. \(\text{PPCM}(a,b) = \dfrac{ab}{\text{PGCD}(a,b)}\).
- Décomposition en facteurs premiers : PGCD = produit des facteurs communs à la puissance minimale ; PPCM = produit de tous les facteurs à la puissance maximale.
- Applications : partages équitables (PGCD), synchronisations et rendez-vous (PPCM), carrelages, horaires.