Arithmétique dans Z

# Arithmétique dans Z ## Introduction L'arithmétique, du grec *arithmos* (nombre), est la reine des mathématiques. Dans ce chapitre, nous explorons les propriétés fondamentales des entiers naturels et relatifs. Ce programme, destiné aux séries C et E, constitue le socle de la théorie des nombres : division euclidienne, bases de numération, divisibilité, congruence, nombres premiers, PGCD, PPCM, identité de Bézout et équations diophantiennes. Ces notions sont essentielles pour la cryptographie moderne, l'informatique et de nombreux domaines des mathématiques pures et appliquées. Nous aborderons chaque point du programme officiel avec rigueur, en fournissant démonstrations complètes et exemples numériques résolus, conformément aux exigences du Baccalauréat camerounais. --- ## I. Division euclidienne dans N ; numération binaire et décimale ### I.1. Division euclidienne dans $\mathbb{N}$ **Théorème (Division euclidienne dans $\mathbb{N}$)** : Pour tout entier naturel $a$ et tout entier naturel non nul $b$, il existe un unique couple $(q, r)$ d'entiers naturels tel que : $$a = bq + r \quad \text{avec} \quad 0 \leq r < b$$ > **À retenir** : $a$ est le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste. La condition $0 \leq r < b$ garantit l'unicité du couple $(q, r)$. **Démonstration** : - **Existence** : Considérons l'ensemble $E = \{a - bk \mid k \in \mathbb{N}, a - bk \geq 0\}$. Cet ensemble est non vide (car $k = 0$ donne $a \in E$) et est une partie non vide de $\mathbb{N}$, donc admet un plus petit élément $r = a - bq$. Par construction, $r \geq 0$. Si $r \geq b$, alors $r - b = a - b(q+1) \geq 0$, ce qui contredit la minimalité de $r$. Donc $0 \leq r < b$. - **Unicité** : Supposons $a = bq_1 + r_1 = bq_2 + r_2$ avec $0 \leq r_1, r_2 < b$. Alors $b(q_1 - q_2) = r_2 - r_1$. Or $|r_2 - r_1| < b$, donc $b|q_1 - q_2| < b$, d'où $|q_1 - q_2| < 1$, donc $q_1 = q_2$ et $r_1 = r_2$. **Exemple** : $a = 257$, $b = 12$. On a $257 = 12 \times 21 + 5$, donc $q = 21$ et $r = 5$. ### I.2. Numération binaire et décimale **Définition** : En base $b$ ($b \geq 2$ entier), tout entier naturel $N$ s'écrit de manière unique sous la forme : $$N = \overline{a_n a_{n-1} \ldots a_1 a_0}_{(b)} = a_n b^n + a_{n-1} b^{n-1} + \ldots + a_1 b + a_0$$ où $a_i \in \{0, 1, \ldots, b-1\}$ pour tout $i$ et $a_n \neq 0$. > **À retenir** : En base $b$, les chiffres utilisés sont $0, 1, \ldots, b-1$. La base 10 (décimale) utilise les chiffres $0$ à $9$ ; la base 2 (binaire) utilise uniquement $0$ et $1$. **Exemple** : $1101_{(2)} = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2 + 1 = 8 + 4 + 0 + 1 = 13$. ### I.3. Passage d'une base à une autre **Méthode de conversion de la base 10 vers une base $b$** : On effectue des divisions euclidiennes successives par $b$ ; les restes successifs, lus de la dernière à la première, donnent les chiffres de l'écriture en base $b$. **Exemple** : Convertir $53$ en base 2. $$53 = 2 \times 26 + 1$$ $$26 = 2 \times 13 + 0$$ $$13 = 2 \times 6 + 1$$ $$6 = 2 \times 3 + 0$$ $$3 = 2 \times 1 + 1$$ $$1 = 2 \times 0 + 1$$ En lisant les restes de bas en haut : $53 = 110101_{(2)}$. **Vérification** : $110101_{(2)} = 32 + 16 + 4 + 1 = 53$. ✓ **Méthode de conversion de la base $b$ vers la base 10** : On développe l'écriture en base $b$ selon la formule de définition. **Exemple** : $2A3_{(16)} = 2 \times 16^2 + 10 \times 16 + 3 = 512 + 160 + 3 = 675$. **Conversion entre bases non décimales** : On passe par la base 10 comme intermédiaire, ou on utilise des regroupements si les bases sont des puissances l'une de l'autre. **Exemple** : Convertir $101110_{(2)}$ en base 8. Comme $8 = 2^3$, on regroupe les chiffres binaires par paquets de 3 à partir de la droite : $101\ 110_{(2)} = 56_{(8)}$. > **À retenir** : Pour convertir un entier d'une base $b_1$ vers une base $b_2$, on peut toujours passer par la base 10. Si $b_2 = b_1^k$, on regroupe les chiffres par paquets de $k$. --- ## II. Divisibilité dans Z, ensemble nZ, congruence ### II.1. Divisibilité dans $\mathbb{Z}$ **Définition** : Soient $a, b \in \mathbb{Z}$. On dit que $b$ divise $a$ (noté $b \mid a$) s'il existe $k \in \mathbb{Z}$ tel que $a = bk$. On dit aussi que $a$ est un multiple de $b$, ou que $b$ est un diviseur de $a$. > **À retenir** : $b \mid a \iff \exists k \in \mathbb{Z}, a = bk$. Si $b \neq 0$, $b \mid a$ équivaut à dire que le reste de la division euclidienne de $a$ par $b$ est nul. **Propriétés fondamentales** : 1. $a \mid a$ (réflexivité) ; si $a \mid b$ et $b \mid a$, alors $a = \pm b$ (antisymétrie à signe près). 2. Si $a \mid b$ et $b \mid c$, alors $a \mid c$ (transitivité). 3. Si $a \mid b$ et $a \mid c$, alors $a \mid (b + c)$ et $a \mid (b - c)$. 4. Si $a \mid b$, alors $a \mid bc$ pour tout $c \in \mathbb{Z}$. 5. Si $a \mid b$ et $a \mid c$, alors $a \mid (ub + vc)$ pour tous $u, v \in \mathbb{Z}$ (combinaison linéaire). **Démonstration de la propriété 3** : Si $a \mid b$ et $a \mid c$, alors $b = ak_1$ et $c = ak_2$ avec $k_1, k_2 \in \mathbb{Z}$. Donc $b + c = a(k_1 + k_2)$, d'où $a \mid (b+c)$. De même, $b - c = a(k_1 - k_2)$, d'où $a \mid (b-c)$. **Exemple** : $3 \mid 12$ et $3 \mid 18$, donc $3 \mid (12 + 18) = 30$ et $3 \mid (2 \times 12 - 5 \times 18) = 24 - 90 = -66$. ### II.2. Ensemble $n\mathbb{Z}$ **Définition** : Pour $n \in \mathbb{Z}$, on note $n\mathbb{Z} = \{nk \mid k \in \mathbb{Z}\}$, l'ensemble des multiples de $n$. > **À retenir** : $n\mathbb{Z}$ est l'ensemble de tous les multiples entiers de $n$. Par exemple, $2\mathbb{Z}$ est l'ensemble des entiers pairs, $3\mathbb{Z} = \{\ldots, -9, -6, -3, 0, 3, 6, 9, \ldots\}$. **Propriétés** : 1. $n\mathbb{Z}$ est stable pour l'addition : si $x, y \in n\mathbb{Z}$, alors $x + y \in n\mathbb{Z}$. 2. $n\mathbb{Z}$ est stable pour la multiplication par un entier quelconque : si $x \in n\mathbb{Z}$ et $k \in \mathbb{Z}$, alors $kx \in n\mathbb{Z}$. 3. $n\mathbb{Z} = m\mathbb{Z} \iff n = \pm m$. 4. $n\mathbb{Z} \subseteq m\mathbb{Z} \iff m \mid n$. **Démonstration de la propriété 4** : Si $n\mathbb{Z} \subseteq m\mathbb{Z}$, alors $n \in m\mathbb{Z}$ (car $n = n \times 1 \in n\mathbb{Z}$), donc $m \mid n$. Réciproquement, si $m \mid n$, alors $n = mk$, donc tout élément $nx \in n\mathbb{Z}$ s'écrit $nx = m(kx) \in m\mathbb{Z}$. ### II.3. Division euclidienne dans $\mathbb{Z}$ **Théorème** : Pour tout $a \in \mathbb{Z}$ et tout $b \in \mathbb{Z}^*$, il existe un unique couple $(q, r) \in \mathbb{Z} \times \mathbb{N}$ tel que : $$a = bq + r \quad \text{avec} \quad 0 \leq r < |b|$$ **Exemple** : $a = -47$, $b = 5$. On a $-47 = 5 \times (-10) + 3$, donc $q = -10$ et $r = 3$. On vérifie : $0 \leq 3 < 5$. ✓ **Remarque** : Le reste est toujours positif ou nul, même lorsque le dividende est négatif. ### II.4. Relation de congruence **Définition** : Soit $n \in \mathbb{N}^*$. Pour $a, b \in \mathbb{Z}$, on dit que $a$ est congru à $b$ modulo $n$, noté $a \equiv b \pmod{n}$, si $n \mid (a - b)$. > **À retenir** : $a \equiv b \pmod{n} \iff n \mid (a-b) \iff a$ et $b$ ont le même reste dans la division euclidienne par $n$. **Exemple** : $17 \equiv 5 \pmod{6}$ car $17 - 5 = 12 = 6 \times 2$. De même, $-3 \equiv 4 \pmod{7}$ car $-3 - 4 = -7 = 7 \times (-1)$. **Propriétés de la congruence** : 1. **Réflexivité** : $a \equiv a \pmod{n}$. 2. **Symétrie** : si $a \equiv b \pmod{n}$, alors $b \equiv a \pmod{n}$. 3. **Transitivité** : si $a \equiv b \pmod{n}$ et $b \equiv c \pmod{n}$, alors $a \equiv c \pmod{n}$. 4. **Compatibilité avec l'addition** : si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors $a + c \equiv b + d \pmod{n}$. 5. **Compatibilité avec la multiplication** : si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors $ac \equiv bd \pmod{n}$. **Démonstration de la compatibilité avec l'addition** : Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors $n \mid (a-b)$ et $n \mid (c-d)$. Donc $n \mid [(a-b) + (c-d)] = (a+c) - (b+d)$, d'où $a + c \equiv b + d \pmod{n}$. **Démonstration de la compatibilité avec la multiplication** : Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors $a = b + nk$ et $c = d + nl$ pour certains $k, l \in \mathbb{Z}$. Donc $ac = (b+nk)(d+nl) = bd + n(bl + kd + nkl)$, d'où $ac - bd = n(bl + kd + nkl)$, et $n \mid (ac - bd)$, donc $ac \equiv bd \pmod{n}$. **Conséquences** : Si $a \equiv b \pmod{n}$, alors pour tout entier $m \geq 1$, $a^m \equiv b^m \pmod{n}$. **Exemple** : Calculer $2^{100} \pmod{7}$. On a $2^3 = 8 \equiv 1 \pmod{7}$. Donc $2^{100} = 2^{3 \times 33 + 1} = (2^3)^{33} \times 2 \equiv 1^{33} \times 2 \equiv 2 \pmod{7}$. > **À retenir** : La congruence est une relation d'équivalence compatible avec l'addition et la multiplication. Elle permet de remplacer un nombre par un autre qui lui est congru pour simplifier les calculs. --- ## III. Critères de divisibilité en base dix ### III.1. Critères fondamentaux **Théorème (Critères de divisibilité)** : Soit $N = \overline{a_n a_{n-1} \ldots a_1 a_0}$ un entier écrit en base 10. 1. **Divisibilité par 2** : $N$ est divisible par 2 $\iff a_0 \in \{0, 2, 4, 6, 8\}$ (le dernier chiffre est pair). 2. **Divisibilité par 3** : $N$ est divisible par 3 $\iff$ la somme de ses chiffres $a_n + a_{n-1} + \ldots + a_0$ est divisible par 3. 3. **Divisibilité par 5** : $N$ est divisible par 5 $\iff a_0 \in \{0, 5\}$. 4. **Divisibilité par 9** : $N$ est divisible par 9 $\iff$ la somme de ses chiffres est divisible par 9. 5. **Divisibilité par 10** : $N$ est divisible par 10 $\iff a_0 = 0$. 6. **Divisibilité par 4** : $N$ est divisible par 4 $\iff$ le nombre formé par les deux derniers chiffres $\overline{a_1 a_0}$ est divisible par 4. 7. **Divisibilité par 25** : $N$ est divisible par 25 $\iff$ le nombre formé par les deux derniers chiffres est divisible par 25. 8. **Divisibilité par 8** : $N$ est divisible par 8 $\iff$ le nombre formé par les trois derniers chiffres est divisible par 8. 9. **Divisibilité par 11** : $N$ est divisible par 11 $\iff$ la différence entre la somme des chiffres de rang pair et la somme des chiffres de rang impair est divisible par 11. > **À retenir** : Les critères de divisibilité par 3 et 9 reposent sur la somme des chiffres ; ceux par 2, 5, 10 sur le dernier chiffre ; ceux par 4, 25 sur les deux derniers chiffres ; celui par 8 sur les trois derniers chiffres ; celui par 11 sur l'alternance des sommes. **Démonstration du critère par 3** : Écrivons $N = \sum_{i=0}^{n} a_i 10^i$. Comme $10 \equiv 1 \pmod{3}$, on a $10^i \equiv 1^i = 1 \pmod{3}$ pour tout $i$. Donc $N \equiv \sum_{i=0}^{n} a_i \pmod{3}$. Ainsi, $3 \mid N \iff N \equiv 0 \pmod{3} \iff \sum a_i \equiv 0 \pmod{3}$. **Démonstration du critère par 11** : Comme $10 \equiv -1 \pmod{11}$, on a $10^i \equiv (-1)^i \pmod{11}$. Donc $N \equiv \sum_{i=0}^{n} a_i (-1)^i = (a_0 + a_2 + a_4 + \ldots) - (a_1 + a_3 + \ldots) \pmod{11}$. **Exemple** : $N = 8472$. Somme des chiffres : $8 + 4 + 7 + 2 = 21$, divisible par 3 mais pas par 9. Donc $3 \mid 8472$ mais $9 \nmid 8472$. Pour 11 : $(2 + 4) - (7 + 8) = 6 - 15 = -9$, non divisible par 11, donc $11 \nmid 8472$. **Exemple** : $N = 9185$. Pour 11 : $(5 + 1) - (8 + 9) = 6 - 17 = -11$, divisible par 11, donc $11 \mid 9185$. Vérification : $9185 = 11 \times 835$. ✓ --- ## IV. Nombres premiers, décomposition en facteurs premiers, crible d'Ératosthène ### IV.1. Nombres premiers **Définition** : Un entier naturel $p \geq 2$ est dit **premier** si ses seuls diviseurs positifs sont 1 et $p$ lui-même. Un entier $n \geq 2$ qui n'est pas premier est dit **composé**. > **À retenir** : Les nombres premiers inférieurs à 30 sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Le nombre 1 n'est ni premier ni composé. Le nombre 2 est le seul nombre premier pair. **Propriété fondamentale** : Tout entier $n \geq 2$ admet au moins un diviseur premier. **Démonstration** : Considérons l'ensemble $D = \{d \in \mathbb{N}^* \mid d \mid n, d \geq 2\}$. Cet ensemble est non vide (car $n \in D$), donc admet un plus petit élément $p$. Si $p$ n'était pas premier, il existerait $d$ avec $2 \leq d < p$ et $d \mid p$, donc $d \mid n$, ce qui contredit la minimalité de $p$. Donc $p$ est premier. **Lemme d'Euclide** : Si $p$ est premier et $p \mid ab$, alors $p \mid a$ ou $p \mid b$. **Démonstration** : Supposons que $p \nmid a$. Alors $\text{PGCD}(p, a) = 1$ (car les seuls diviseurs de $p$ sont 1 et $p$, et $p$ ne divise pas $a$). Par le théorème de Bézout (démontré plus loin), il existe $u, v \in \mathbb{Z}$ tels que $up + va = 1$. Multiplions par $b$ : $upb + vab = b$. Comme $p \mid ab$, on a $p \mid vab$, et $p \mid upb$, donc $p \mid (upb + vab) = b$. Donc $p \mid b$. ### IV.2. Décomposition en produit de puissances de nombres premiers **Théorème fondamental de l'arithmétique** : Tout entier $n \geq 2$ se décompose de manière unique (à l'ordre des facteurs près) en produit de puissances de nombres premiers : $$n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \ldots \times p_k^{\alpha_k}$$ où $p_1 < p_2 < \ldots < p_k$ sont des nombres premiers distincts et $\alpha_1, \alpha_2, \ldots, \alpha_k \in \mathbb{N}^*$. > **À retenir** : Cette décomposition est unique. Par exemple, $360 = 2^3 \times 3^2 \times 5$. **Démonstration de l'existence** : Par récurrence forte sur $n$. Pour $n = 2$, c'est évident. Supposons la propriété vraie pour tout entier $< n$. Si $n$ est premier, c'est fini. Sinon, $n = ab$ avec $2 \leq a, b < n$. Par hypothèse de récurrence, $a$ et $b$ se décomposent en produits de nombres premiers, donc $n$ aussi. **Démonstration de l'unicité** : Supposons $n = p_1^{\alpha_1} \ldots p_k^{\alpha_k} = q_1^{\beta_1} \ldots q_l^{\beta_l}$. Alors $p_1 \mid q_1^{\beta_1} \ldots q_l^{\beta_l}$. Par le lemme d'Euclide appliqué itérativement, $p_1$ divise l'un des $q_j$, donc $p_1 = q_j$ (car $q_j$ est premier). On simplifie et on répète le raisonnement. **Méthode de décomposition** : On divise successivement par les nombres premiers dans l'ordre croissant. **Exemple** : Décomposer 2520. $$2520 = 2 \times 1260 = 2^2 \times 630 = 2^3 \times 315 = 2^3 \times 3 \times 105 = 2^3 \times 3^2 \times 35 = 2^3 \times 3^2 \times 5 \times 7$$ Donc $2520 = 2^3 \times 3^2 \times 5 \times 7$. ### IV.3. Crible d'Ératosthène de Cyrène **Méthode** : Pour trouver tous les nombres premiers inférieurs ou égaux à un entier $N$ : 1. Écrire tous les entiers de 2 à $N$. 2. Barrer tous les multiples de 2 strictement supérieurs à 2. 3. Prendre le premier nombre non barré (3), barrer tous ses multiples strictement supérieurs à 3. 4. Continuer avec le nombre premier suivant non barré, jusqu'à dépasser $\sqrt{N}$. 5. Les nombres non barrés sont les nombres premiers. > **À retenir** : Le crible d'Ératosthène repose sur le fait que si $n$ est composé, il admet un diviseur premier $p \leq \sqrt{n}$. **Justification** : Si $n$ est composé, $n = ab$ avec $2 \leq a \leq b$. Alors $a^2 \leq ab = n$, donc $a \leq \sqrt{n}$. Le plus petit diviseur premier de $n$ est $\leq a \leq \sqrt{n}$. **Exemple** : Nombres premiers $\leq 50$ par le crible : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. **Application** : Vérifier si 97 est premier. $\sqrt{97} \approx 9,85$. On teste la divisibilité par les nombres premiers $\leq 9$ : 2, 3, 5, 7. $97$ n'est divisible par aucun, donc 97 est premier. --- ## V. PGCD et PPCM de deux entiers ### V.1. Définitions **Définition (PGCD)** : Soient $a, b \in \mathbb{Z}$ non tous deux nuls. Le **Plus Grand Commun Diviseur** de $a$ et $b$, noté $\text{PGCD}(a, b)$ ou $a \wedge b$, est le plus grand entier positif qui divise à la fois $a$ et $b$. **Définition (PPCM)** : Soient $a, b \in \mathbb{Z}^*$. Le **Plus Petit Commun Multiple** de $a$ et $b$, noté $\text{PPCM}(a, b)$ ou $a \vee b$, est le plus petit entier positif qui est multiple à la fois de $a$ et de $b$. > **À retenir** : $\text{PGCD}(a, b)$ est le plus grand entier positif divisant $a$ et $b$. $\text{PPCM}(a, b)$ est le plus petit entier positif multiple de $a$ et de $b$. Par convention, $\text{PGCD}(0, 0) = 0$. **Exemple** : $\text{PGCD}(12, 18) = 6$ ; $\text{PPCM}(12, 18) = 36$. ### V.2. Algorithme d'Euclide **Théorème (Lemme d'Euclide)** : Pour $a, b \in \mathbb{Z}$ avec $b \neq 0$, si $a = bq + r$ (division euclidienne), alors $\text{PGCD}(a, b) = \text{PGCD}(b, r)$. **Démonstration** : Tout diviseur commun de $a$ et $b$ divise $a - bq = r$, donc divise $b$ et $r$. Réciproquement, tout diviseur commun de $b$ et $r$ divise $bq + r = a$, donc divise $a$ et $b$. Les ensembles de diviseurs communs coïncident, donc les PGCD sont égaux. **Algorithme d'Euclide** : On effectue des divisions euclidiennes successives : $$a = bq_1 + r_1 \quad (0 \leq r_1 < b)$$ $$b = r_1 q_2 + r_2 \quad (0 \leq r_2 < r_1)$$ $$r_1 = r_2 q_3 + r_3 \quad (0 \leq r_3 < r_2)$$ $$\vdots$$ $$r_{n-2} = r_{n-1} q_n + r_n \quad (0 \leq r_n < r_{n-1})$$ $$r_{n-1} = r_n q_{n+1} + 0$$ La suite des restes est strictement décroissante, donc l'algorithme se termine. Le dernier reste non nul $r_n$ est le PGCD. > **À retenir** : L'algorithme d'Euclide fournit le PGCD par divisions euclidiennes successives. Le dernier reste non nul est le PGCD. **Exemple** : Calculer $\text{PGCD}(252, 198)$. $$252 = 198 \times 1 + 54$$ $$198 = 54 \times 3 + 36$$ $$54 = 36 \times 1 + 18$$ $$36 = 18 \times 2 + 0$$ Le dernier reste non nul est 18, donc $\text{PGCD}(252, 198) = 18$. ### V.3. PGCD par décomposition en facteurs premiers **Méthode** : On décompose $a$ et $b$ en produits de facteurs premiers. Le PGCD est le produit des facteurs premiers communs, chacun affecté du plus petit exposant. **Exemple** : $a = 2520 = 2^3 \times 3^2 \times 5 \times 7$ et $b = 1980 = 2^2 \times 3^2 \times 5 \times 11$. $\text{PGCD}(2520, 1980) = 2^2 \times 3^2 \times 5 = 4 \times 9 \times 5 = 180$. ### V.4. PPCM **Méthode par décomposition** : Le PPCM est le produit des facteurs premiers présents dans l'une ou l'autre décomposition, chacun affecté du plus grand exposant. **Exemple** : Avec $a = 2520$ et $b = 1980$ ci-dessus : $\text{PPCM}(2520, 1980) = 2^3 \times 3^2 \times 5 \times 7 \times 11 = 8 \times 9 \times 5 \times 7 \times 11 = 27720$. **Relation fondamentale** : Pour tous $a, b \in \mathbb{Z}^*$ : $$\text{PGCD}(a, b) \times \text{PPCM}(a, b) = |a \times b|$$ > **À retenir** : $a \wedge b \times a \vee b = |ab|$. Cette relation permet de calculer le PPCM dès qu'on connaît le PGCD. **Démonstration** : Soient $a = \prod p_i^{\alpha_i}$ et $b = \prod p_i^{\beta_i}$ (avec $\alpha_i, \beta_i \geq 0$). Alors $\text{PGCD}(a,b) = \prod p_i^{\min(\alpha_i, \beta_i)}$ et $\text{PPCM}(a,b) = \prod p_i^{\max(\alpha_i, \beta_i)}$. Donc $\text{PGCD}(a,b) \times \text{PPCM}(a,b) = \prod p_i^{\min(\alpha_i,\beta_i) + \max(\alpha_i,\beta_i)} = \prod p_i^{\alpha_i + \beta_i} = |ab|$. **Vérification** : $180 \times 27720 = 4989600 = 2520 \times 1980$. ✓ ### V.5. Propriétés du PGCD et du PPCM 1. $\text{PGCD}(a, b) = \text{PGCD}(b, a)$ (commutativité). 2. $\text{PGCD}(a, 0) = |a|$ ; $\text{PGCD}(a, 1) = 1$. 3. $\text{PGCD}(ka, kb) = |k| \times \text{PGCD}(a, b)$ pour tout $k \in \mathbb{Z}$. 4. Si $d = \text{PGCD}(a, b)$, alors $\text{PGCD}\left(\frac{a}{d}, \frac{b}{d}\right) = 1$. 5. Si $c \mid a$ et $c \mid b$, alors $c \mid \text{PGCD}(a, b)$. 6. $\text{PPCM}(ka, kb) = |k| \times \text{PPCM}(a, b)$. **Démonstration de la propriété 4** : Soit $d = \text{PGCD}(a, b)$. Alors $a = da'$ et $b = db'$ avec $a', b' \in \mathbb{Z}$. Si $e = \text{PGCD}(a', b') > 1$, alors $de$ divise $a$ et $b$, et $de > d$, contradiction. Donc $\text{PGCD}(a', b') = 1$. --- ## VI. Nombres premiers entre eux, identité de Bézout, propriété de Gauss ### VI.1. Nombres premiers entre eux **Définition** : Deux entiers $a$ et $b$ sont dits **premiers entre eux** (ou étrangers) si $\text{PGCD}(a, b) = 1$. > **À retenir** : $a$ et $b$ sont premiers entre eux $\iff$ ils n'ont aucun diviseur premier commun $\iff$ $\text{PGCD}(a, b) = 1$. **Exemple** : 15 et 28 sont premiers entre eux car $15 = 3 \times 5$ et $28 = 2^2 \times 7$ n'ont aucun facteur premier commun. ### VI.2. Identité de Bézout **Théorème (Identité de Bézout)** : Soient $a, b \in \mathbb{Z}$ non tous deux nuls, et $d = \text{PGCD}(a, b)$. Il existe $u, v \in \mathbb{Z}$ tels que : $$au + bv = d$$ **Corollaire (Théorème de Bézout)** : $a$ et $b$ sont premiers entre eux $\iff$ il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. > **À retenir** : L'identité de Bézout exprime le PGCD comme combinaison linéaire de $a$ et $b$. En particulier, $a$ et $b$ sont premiers entre eux si et seulement si on peut écrire $au + bv = 1$. **Démonstration** : Considérons l'ensemble $E = \{au + bv \mid u, v \in \mathbb{Z}, au + bv > 0\}$. $E$ est une partie non vide de $\mathbb{N}^*$ (car $|a| = a \times \text{signe}(a) + b \times 0 \in E$ si $a \neq 0$). Soit $d_0$ le plus petit élément de $E$. Montrons que $d_0 = d = \text{PGCD}(a, b)$. - $d_0 = au_0 + bv_0$ pour certains $u_0, v_0$. Soit $r$ le reste de la division euclidienne de $a$ par $d_0$ : $a = d_0 q + r$ avec $0 \leq r < d_0$. Alors $r = a - d_0 q = a - (au_0 + bv_0)q = a(1 - u_0 q) + b(-v_0 q)$. Si $r > 0$, alors $r \in E$ et $r < d_0$, contradiction. Donc $r = 0$, et $d_0 \mid a$. De même, $d_0 \mid b$. Donc $d_0$ est un diviseur commun de $a$ et $b$, d'où $d_0 \leq d$. - Réciproquement, $d \mid a$ et $d \mid b$, donc $d \mid (au_0 + bv_0) = d_0$, d'où $d \leq d_0$. - Conclusion : $d = d_0$. **Méthode pratique (algorithme d'Euclide étendu)** : On remonte l'algorithme d'Euclide pour exprimer le PGCD comme combinaison linéaire. **Exemple** : Trouver $u, v$ tels que $252u + 198v = 18$. Reprenons les divisions de l'algorithme d'Euclide : $$252 = 198 \times 1 + 54 \quad \Rightarrow \quad 54 = 252 - 198$$ $$198 = 54 \times 3 + 36 \quad \Rightarrow \quad 36 = 198 - 54 \times 3$$ $$54 = 36 \times 1 + 18 \quad \Rightarrow \quad 18 = 54 - 36$$ En remontant : $$18 = 54 - 36 = 54 - (198 - 54 \times 3) = 54 \times 4 - 198$$ $$18 = (252 - 198) \times 4 - 198 = 252 \times 4 - 198 \times 5$$ Donc $u = 4$ et $v = -5$. Vérification : $252 \times 4 + 198 \times (-5) = 1008 - 990 = 18$. ✓ ### VI.3. Propriété de Gauss **Théorème (Lemme de Gauss)** : Si $a \mid bc$ et $\text{PGCD}(a, b) = 1$, alors $a \mid c$. > **À retenir** : Le lemme de Gauss : si $a$ divise un produit $bc$ et que $a$ est premier avec $b$, alors $a$ divise $c$. C'est une généralisation du lemme d'Euclide (cas où $a$ est premier). **Démonstration** : Puisque $\text{PGCD}(a, b) = 1$, par Bézout, il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. Multiplions par $c$ : $auc + bvc = c$. Comme $a \mid bc$, on a $a \mid bvc$. De plus $a \mid auc$. Donc $a \mid (auc + bvc) = c$. **Corollaire** : Si $a \mid c$, $b \mid c$ et $\text{PGCD}(a, b) = 1$, alors $ab \mid c$. **Démonstration** : $b \mid c$ donc $c = bk$. Comme $a \mid c = bk$ et $\text{PGCD}(a, b) = 1$, par Gauss, $a \mid k$. Donc $k = ak'$, d'où $c = bak'$, et $ab \mid c$. **Exemple** : Montrer que $6 \mid n(n+1)(n+2)$ pour tout entier $n$. Parmi trois entiers consécutifs, l'un est divisible par 3 et au moins un est pair (divisible par 2). Donc $2 \mid n(n+1)(n+2)$ et $3 \mid n(n+1)(n+2)$. Comme $\text{PGCD}(2, 3) = 1$, par le corollaire, $6 \mid n(n+1)(n+2)$. --- ## VII. Équation diophantienne $ax + by = c$ dans $\mathbb{Z} \times \mathbb{Z}$ ### VII.1. Définition et condition d'existence **Définition** : Une équation diophantienne est une équation de la forme $ax + by = c$ où $a, b, c \in \mathbb{Z}$ sont donnés et où l'on cherche les solutions $(x, y) \in \mathbb{Z} \times \mathbb{Z}$. **Théorème (Condition d'existence)** : L'équation $ax + by = c$ admet des solutions entières $\iff$ $\text{PGCD}(a, b) \mid c$. > **À retenir** : L'équation $ax + by = c$ a des solutions dans $\mathbb{Z}^2$ si et seulement si le PGCD de $a$ et $b$ divise $c$. **Démonstration** : - **Condition nécessaire** : Si $(x_0, y_0)$ est solution, alors $c = ax_0 + by_0$. Comme $d = \text{PGCD}(a, b)$ divise $a$ et $b$, $d$ divise $ax_0 + by_0 = c$. - **Condition suffisante** : Si $d \mid c$, alors $c = dk$ avec $k \in \mathbb{Z}$. Par Bézout, il existe $u, v \in \mathbb{Z}$ tels que $au + bv = d$. Alors $a(uk) + b(vk) = dk = c$. Donc $(x_0, y_0) = (uk, vk)$ est une solution particulière. ### VII.2. Résolution complète **Théorème (Structure des solutions)** : Soit $d = \text{PGCD}(a, b)$ avec $d \mid c$. Si $(x_0, y_0)$ est une solution particulière de $ax + by = c$, alors toutes les solutions sont données par : $$\begin{cases} x = x_0 + \frac{b}{d} t \\ y = y_0 - \frac{a}{d} t \end{cases} \quad \text{pour } t \in \mathbb{Z}$$ > **À retenir** : Une fois une solution particulière trouvée, toutes les solutions s'obtiennent en ajoutant des multiples de $\frac{b}{d}$ à $x$ et en retranchant des multiples de $\frac{a}{d}$ à $y$. **Démonstration** : - **Vérification** : $a\left(x_0 + \frac{b}{d}t\right) + b\left(y_0 - \frac{a}{d}t\right) = ax_0 + by_0 + \frac{ab}{d}t - \frac{ab}{d}t = c$. Donc toutes ces paires sont solutions. - **Réciproque** : Soit $(x, y)$ une solution quelconque. Alors $a(x - x_0) + b(y - y_0) = 0$, donc $a(x - x_0) = -b(y - y_0)$. Divisons par $d$ : $\frac{a}{d}(x - x_0) = -\frac{b}{d}(y - y_0)$. Comme $\text{PGCD}\left(\frac{a}{d}, \frac{b}{d}\right) = 1$ et $\frac{a}{d} \mid \frac{b}{d}(y - y_0)$, par Gauss, $\frac{a}{d} \mid (y - y_0)$. Donc $y - y_0 = \frac{a}{d} t$ pour un certain $t \in \mathbb{Z}$, d'où $y = y_0 - \frac{a}{d}(-t)$. En posant $t' = -t$, on obtient la forme annoncée. De même pour $x$. ### VII.3. Méthode de résolution 1. Calculer $d = \text{PGCD}(a, b)$. 2. Vérifier que $d \mid c$. Sinon, pas de solution. 3. Simplifier l'équation en divisant par $d$ : $a'x + b'y = c'$ avec $\text{PGCD}(a', b') = 1$. 4. Trouver une solution particulière $(x_0, y_0)$ (par l'algorithme d'Euclide étendu ou par tâtonnement). 5. Écrire toutes les solutions avec le paramètre $t$. **Exemple** : Résoudre dans $\mathbb{Z}^2$ l'équation $252x + 198y = 36$. **Étape 1** : $d = \text{PGCD}(252, 198) = 18$ (calculé précédemment). **Étape 2** : $18 \mid 36$, donc des solutions existent. **Étape 3** : On simplifie : $14x + 11y = 2$ (en divisant par 18). **Étape 4** : Cherchons une solution particulière. On a vu que $252 \times 4 + 198 \times (-5) = 18$. En multipliant par 2 : $252 \times 8 + 198 \times (-10) = 36$. Donc $(x_0, y_0) = (8, -10)$ est une solution particulière. Vérifions sur l'équation simplifiée : $14 \times 8 + 11 \times (-10) = 112 - 110 = 2$. ✓ **Étape 5** : Toutes les solutions sont : $$\begin{cases} x = 8 + \frac{198}{18} t = 8 + 11t \\ y = -10 - \frac{252}{18} t = -10 - 14t \end{cases} \quad t \in \mathbb{Z}$$ **Vérification** : $252(8 + 11t) + 198(-10 - 14t) = 2016 + 2772t - 1980 - 2772t = 36$. ✓ **Exemple** : Résoudre $3x + 6y = 5$. $d = \text{PGCD}(3, 6) = 3$. Or $3 \nmid 5$. Donc l'équation n'a **aucune solution** dans $\mathbb{Z}^2$. **Exemple** : Résoudre $2x + 3y = 1$. $d = \text{PGCD}(2, 3) = 1$, et $1 \mid 1$, donc des solutions existent. On cherche une solution particulière : $2 \times (-1) + 3 \times 1 = 1$, donc $(x_0, y_0) = (-1, 1)$. Toutes les solutions : $$\begin{cases} x = -1 + 3t \\ y = 1 - 2t \end{cases} \quad t \in \mathbb{Z}$$ **Vérification** : $2(-1 + 3t) + 3(1 - 2t) = -2 + 6t + 3 - 6t = 1$. ✓ --- ## Conclusion L'arithmétique dans $\mathbb{Z}$ constitue un pilier fondamental des mathématiques. Nous avons parcouru l'ensemble du programme officiel : la division euclidienne qui garantit l'unicité du quotient et du reste, les systèmes de numération avec les conversions entre bases, la divisibilité et la congruence avec leurs propriétés de compatibilité, les critères de divisibilité en base 10, les nombres premiers avec le théorème fondamental de l'arithmétique et le crible d'Ératosthène, le PGCD et le PPCM avec l'algorithme d'Euclide, l'identité de Bézout et le lemme de Gauss, et enfin les équations diophantiennes linéaires. Ces outils, apparemment abstraits, trouvent des applications concrètes majeures : cryptographie RSA (basée sur les nombres premiers et la congruence), codes correcteurs d'erreurs, algorithmique, horlogerie (congruence modulo 12 ou 24), calendriers, etc. La maîtrise de ces concepts est indispensable pour aborder sereinement les épreuves du Baccalauréat camerounais et pour poursuivre des études supérieures en mathématiques, informatique ou ingénierie. L'approche par compétences du programme MINESEC met l'accent sur la résolution de problèmes et le raisonnement rigoureux, compétences que ce chapitre développe pleinement.