L’arithmétique est l’étude des propriétés des nombres entiers relatifs, en particulier de la divisibilité. Ce chapitre développe les outils essentiels : division euclidienne, plus grand commun diviseur (PGCD), plus petit commun multiple (PPCM), nombres premiers, et les théorèmes fondamentaux de Bézout et de Gauss. Ces notions, propres au programme de la filière Sciences Mathématiques, sont à la base de nombreuses applications : simplification de fractions, résolution d’équations à solutions entières, cryptographie.
Divisibilité dans ℤ
Soit a et b deux entiers relatifs. On dit que a divise b (noté a | b) s’il existe un entier relatif k tel que b = k × a. On dit aussi que b est un multiple de a, ou que a est un diviseur de b. Propriétés essentielles : (i) si a | b et b | c, alors a | c (transitivité) ; (ii) si a | b et a | c, alors pour tous entiers relatifs u et v, a | (bu + cv) (combinaison linéaire) ; (iii) si a et b sont des entiers naturels non nuls tels que a | b et b | a, alors a = b.
Exemple : puisque 3 | 15 et 3 | 9, la propriété de combinaison linéaire assure que 3 divise 2×15 − 5×9 = 30 − 45 = −15, ce que l’on vérifie directement : −15 ÷ 3 = −5, donc bien 3 | (−15).
Division euclidienne dans ℤ
Théorème (division euclidienne) : pour tout entier relatif a et tout entier b non nul, il existe un unique couple d’entiers (q, r) tel que a = b × q + r avec 0 ≤ r < |b|. L’entier q est appelé quotient et r le reste de la division euclidienne de a par b. On dit que b divise a si et seulement si le reste r de cette division est nul.
Exemple : effectuons la division euclidienne de 157 par 12. On cherche le plus grand multiple de 12 inférieur ou égal à 157 : 12 × 13 = 156, donc 157 = 12 × 13 + 1, avec 0 ≤ 1 < 12. Le quotient est q = 13 et le reste est r = 1.
PGCD et algorithme d’Euclide
Le plus grand commun diviseur de deux entiers naturels non nuls a et b, noté PGCD(a, b), est le plus grand des diviseurs communs à a et b. L’algorithme d’Euclide repose sur la propriété PGCD(a, b) = PGCD(b, r), où r est le reste de la division euclidienne de a par b (avec b ≠ 0) : on répète les divisions euclidiennes successives jusqu’à obtenir un reste nul ; le PGCD est alors le dernier reste non nul.
Exemple : calculons PGCD(252, 198). 252 = 198 × 1 + 54 ; 198 = 54 × 3 + 36 ; 54 = 36 × 1 + 18 ; 36 = 18 × 2 + 0. Le dernier reste non nul est 18, donc PGCD(252, 198) = 18.
PPCM, nombres premiers entre eux et théorème de Bézout
Le plus petit commun multiple de deux entiers naturels non nuls a et b, noté PPCM(a, b), est le plus petit des multiples communs strictement positifs de a et b. Il vérifie la relation fondamentale : PGCD(a, b) × PPCM(a, b) = a × b. Deux entiers a et b sont dits premiers entre eux lorsque PGCD(a, b) = 1. Le théorème de Bézout affirme que a et b sont premiers entre eux si et seulement s’il existe deux entiers relatifs u et v tels que au + bv = 1 (plus généralement, si PGCD(a,b) = d, il existe u, v tels que au + bv = d) ; les entiers u et v s’obtiennent par « remontée » de l’algorithme d’Euclide.
Exemple : reprenons PGCD(252, 198) = 18 trouvé ci-dessus. On a PPCM(252, 198) = (252 × 198) ÷ 18 = 49896 ÷ 18 = 2772. Pour Bézout, on remonte l’algorithme d’Euclide : 18 = 54 − 36×1 ; en remplaçant 36 = 198 − 54×3, on obtient 18 = 54 − (198 − 54×3) = 4×54 − 198 ; en remplaçant enfin 54 = 252 − 198, on obtient 18 = 4×(252 − 198) − 198 = 4×252 − 5×198. On vérifie : 4×252 − 5×198 = 1008 − 990 = 18. On a donc trouvé u = 4 et v = −5.
Nombres premiers, décomposition en facteurs premiers et théorème de Gauss
Un entier naturel p ≥ 2 est premier si ses seuls diviseurs positifs sont 1 et p. Tout entier naturel n ≥ 2 se décompose, de façon unique à l’ordre des facteurs près, en un produit de nombres premiers (théorème fondamental de l’arithmétique). Le théorème de Gauss énonce : si a divise le produit bc, et si a est premier avec b (PGCD(a, b) = 1), alors a divise c.
Exemple : 360 = 2³ × 3² × 5 est la décomposition en facteurs premiers de 360 (on vérifie : 8 × 9 × 5 = 360). Pour le théorème de Gauss : si 11 divise 15n, et comme PGCD(11, 15) = 1 (11 est premier et ne divise pas 15), le théorème de Gauss permet de conclure que 11 divise n.
Exercices
1. Effectuer la division euclidienne de 875 par 23 : donner le quotient q et le reste r.
2. Calculer PGCD(462, 273) à l’aide de l’algorithme d’Euclide, en détaillant toutes les étapes.
3. En utilisant le résultat de l’exercice précédent, calculer PPCM(462, 273).
4. En remontant l’algorithme d’Euclide de l’exercice 2, trouver un couple d’entiers relatifs (u, v) tel que 462u + 273v = 21.
5. En utilisant le PGCD(462, 273) = 21, écrire la fraction 462/273 sous forme irréductible.
6. Démontrer que si un entier n vérifie 15 | 8n, alors 15 | n (on calculera au préalable PGCD(15, 8) par l’algorithme d’Euclide).
7. Trouver tous les couples (a, b) d’entiers naturels non nuls tels que PGCD(a, b) = 6 et PPCM(a, b) = 180.
Corrigés
1.
On cherche le plus grand multiple de 23 inférieur ou égal à 875. On a 23 × 38 = 874, et 875 − 874 = 1, avec bien 0 ≤ 1 < 23. Donc 875 = 23 × 38 + 1 : le quotient est q = 38 et le reste est r = 1.
2.
On applique l’algorithme d’Euclide par divisions euclidiennes successives : 462 = 273 × 1 + 189 ; 273 = 189 × 1 + 84 ; 189 = 84 × 2 + 21 ; 84 = 21 × 4 + 0. Le dernier reste non nul est 21, donc PGCD(462, 273) = 21.
3.
On utilise la relation PGCD(a, b) × PPCM(a, b) = a × b, avec a = 462, b = 273 et PGCD(462, 273) = 21 (trouvé à l’exercice 2). On a 462 × 273 = 126126, donc PPCM(462, 273) = 126126 ÷ 21 = 6006.
4.
On remonte les trois divisions euclidiennes de l’exercice 2 (en ignorant la dernière, de reste nul) : (i) 189 = 462 − 273×1 ; (ii) 84 = 273 − 189×1 ; (iii) 21 = 189 − 84×2.
À partir de (iii) : 21 = 189 − 2×84. On remplace 84 par (ii) : 21 = 189 − 2×(273 − 189) = 189 − 2×273 + 2×189 = 3×189 − 2×273.
On remplace ensuite 189 par (i) : 21 = 3×(462 − 273) − 2×273 = 3×462 − 3×273 − 2×273 = 3×462 − 5×273.
Vérification : 3×462 = 1386, 5×273 = 1365, et 1386 − 1365 = 21. On a donc trouvé u = 3 et v = −5.
5.
On sait que PGCD(462, 273) = 21. On divise numérateur et dénominateur par ce PGCD : 462 ÷ 21 = 22 et 273 ÷ 21 = 13. La fraction devient 22/13. Comme 13 est un nombre premier qui ne divise pas 22, PGCD(22, 13) = 1 : la fraction 22/13 est bien sous forme irréductible.
6.
On calcule d’abord PGCD(15, 8) par l’algorithme d’Euclide : 15 = 8×1 + 7 ; 8 = 7×1 + 1 ; 7 = 1×7 + 0. Le dernier reste non nul est 1, donc PGCD(15, 8) = 1 : les entiers 15 et 8 sont premiers entre eux.
On a par hypothèse 15 | 8n, c’est-à-dire 15 divise le produit 8 × n. Comme PGCD(15, 8) = 1 (15 est premier avec 8), le théorème de Gauss permet de conclure directement que 15 divise n, c’est-à-dire 15 | n.
7.
Comme PGCD(a, b) = 6, on peut écrire a = 6a′ et b = 6b′ avec PGCD(a′, b′) = 1. On sait que PGCD(a,b) × PPCM(a,b) = a × b, donc PPCM(a, b) = (a × b) ÷ PGCD(a,b) = (36 a′b′) ÷ 6 = 6 a′b′. L’équation PPCM(a, b) = 180 devient donc 6 a′b′ = 180, soit a′b′ = 30, avec la condition PGCD(a′, b′) = 1.
On cherche tous les couples d’entiers naturels non nuls (a′, b′) de produit 30 et premiers entre eux : les diviseurs de 30 sont 1, 2, 3, 5, 6, 10, 15, 30. En testant les décompositions : 1×30 (PGCD 1, convient), 2×15 (PGCD 1, convient), 3×10 (PGCD 1, convient), 5×6 (PGCD 1, convient). La décomposition 6×5 redonne le même couple que 5×6 (à l’ordre près), de même pour les autres.
En revenant à (a, b) = (6a′, 6b′), on obtient les couples solutions (à l’ordre près) : (6, 180), (12, 90), (18, 60), (30, 36) ainsi que leurs symétriques en échangeant a et b.
