Arithmétique

## Objectifs et prérequis **Objectifs** : À la fin de ce chapitre, l’élève pourra - définir le PGCD et le PPCM de deux entiers naturels ; - appliquer l’algorithme des soustractions et l’algorithme d’Euclide pour calculer le PGCD ; - démontrer la relation $a \times b = \operatorname{PGCD}(a,b) \times \operatorname{PPCM}(a,b)$ ; - résoudre des problèmes simples utilisant ces notions (fractions, problèmes de partage, etc.). **Prérequis** : maîtrise des opérations sur les entiers naturels, connaissance des diviseurs et des multiples, savoir écrire une égalité sous forme factorisée. ## Introduction L’arithmétique des entiers naturels repose sur deux concepts fondamentaux : le plus grand commun diviseur (PGCD) et le plus petit commun multiple (PPCM). Ils apparaissent naturellement lorsqu’on cherche à simplifier une fraction, à régler un problème de répartition ou à déterminer la périodicité de deux phénomènes. Le programme officiel du secondaire camerounais (MINESEC/IGE) propose trois leçons : le PGCD par l’algorithme des soustractions, le PGCD par l’algorithme d’Euclide, puis la relation entre PGCD et PPCM. Nous les traiterons successivement, en insistant sur les démonstrations et les exemples résolus pas à pas. ## I. PGCD - algorithme des soustractions ### Définition > Le **PGCD** de deux entiers naturels $a$ et $b$ (non nuls simultanément) est le plus grand entier qui divise à la fois $a$ et $b$. On le note $\operatorname{PGCD}(a,b)$. ### Propriétés > 1. $\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b,a)$. > 2. Si $a=b\cdot q+r$ avec $0\le r<b$, alors $\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b,r)$. > 3. Si $a>b$, alors $\operatorname{PGCD}(a,b)=\operatorname{PGCD}(a-b,b)$. ### Démonstration de la propriété 3 (soustractions) Soit $d=\operatorname{PGCD}(a,b)$. Alors $d\mid a$ et $d\mid b$, donc $d\mid (a-b)$. Réciproquement, si $e$ divise $a-b$ et $b$, alors $e$ divise $(a-b)+b=a$. Ainsi $e$ divise aussi bien $a$ que $b$, donc $e\le d$. Donc $\operatorname{PGCD}(a-b,b)=d$. ### Algorithme des soustractions 1. Tant que $a\neq b$ : - si $a>b$, remplacer $a$ par $a-b$ ; - sinon remplacer $b$ par $b-a$. 2. Lorsque $a=b$, cette valeur commune est le PGCD. L’algorithme termine parce que à chaque étape la somme $a+b$ diminue strictement et reste positive. ### Exemple 1 (simple) Calculer $\operatorname{PGCD}(48,18)$ par soustractions. | Étape | $a$ | $b$ | Action | |------|-----|-----|--------| | 0 | 48 | 18 | $a>b$ → $a:=48-18=30$ | | 1 | 30 | 18 | $a>b$ → $a:=30-18=12$ | | 2 | 12 | 18 | $b>a$ → $b:=18-12=6$ | | 3 | 12 | 6 | $a>b$ → $a:=12-6=6$ | | 4 | 6 | 6 | arrêt → PGCD = 6 | ### Exemple 2 (délicat) Calculer $\operatorname{PGCD}(273,105)$. - $273>105$ → $a:=273-105=168$ - $168>105$ → $a:=168-105=63$ - $105>63$ → $b:=105-63=42$ - $63>42$ → $a:=63-42=21$ - $42>21$ → $b:=42-21=21$ - $a=b=21$ → PGCD = 21 On vérifie : $273=21\times13$, $105=21\times5$. ## II. PGCD - algorithme d’Euclide ### Définition (reste) Pour des entiers $a\ge0$ et $b>0$, il existe uniques $q$ (quotient) et $r$ (reste) tels que $a=bq+r$ avec $0\le r<b$. ### Propriété fondamentale > $\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b,r)$ où $r$ est le reste de la division de $a$ par $b$. ### Démonstration Soit $d=\operatorname{PGCD}(a,b)$. Alors $d\mid a$ et $d\mid b$, donc $d\mid (a-bq)=r$. Réciproquement, si $e$ divise $b$ et $r$, alors $e$ divise $bq+r=a$. Ainsi $e$ divise $a$ et $b$, donc $e\le d$. Donc $\operatorname{PGCD}(b,r)=d$. ### Algorithme d’Euclide 1. Tant que $b\neq0$ : - calculer $r = a \bmod b$ ; - remplacer $(a,b)$ par $(b,r)$. 2. Lorsque $b=0$, le PGCD vaut $a$. Cet algorithme termine parce que les restes forment une suite strictement décroissante d’entiers naturels, donc atteinte de $0$ après un nombre fini d’étapes. Sa complexité est en $O(\log \min(a,b))$. ### Exemple 1 (simple) $\operatorname{PGCD}(48,18)$ : - $48 = 18\times2 + 12$ → $(a,b)=(18,12)$ - $18 = 12\times1 + 6$ → $(a,b)=(12,6)$ - $12 = 6\times2 + 0$ → arrêt, PGCD = 6. ### Exemple 2 (délicat) $\operatorname{PGCD}(273,105)$ : - $273 = 105\times2 + 63$ → $(105,63)$ - $105 = 63\times1 + 42$ → $(63,42)$ - $63 = 42\times1 + 21$ → $(42,21)$ - $42 = 21\times2 + 0$ → arrêt, PGCD = 21. ## III. Relation entre le PPCM et le PGCD de deux entiers naturels ### Définition du PPCM > Le **PPCM** de deux entiers naturels $a$ et $b$ (non nuls simultanément) est le plus petit entier positif qui est multiple de $a$ et de $b$. On le note $\operatorname{PPCM}(a,b)$. ### Propriété essentielle > Pour tout $a,b\in\mathbb{N}^{*}$ : > $$ a \times b = \operatorname{PGCD}(a,b) \times \operatorname{PPCM}(a,b). $$ ### Démonstration Écrivons la factorisation première de $a$ et $b$ : $$ a = \prod_{i} p_i^{\alpha_i}, \qquad b = \prod_{i} p_i^{\beta_i}, $$ où $\alpha_i,\beta_i\ge0$. Alors $$ \operatorname{PGCD}(a,b)=\prod_{i} p_i^{\min(\alpha_i,\beta_i)}, \qquad \operatorname{PPCM}(a,b)=\prod_{i} p_i^{\max(\alpha_i,\beta_i)}. $$ Le produit des deux donne $$ \prod_{i} p_i^{\min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i)} = \prod_{i} p_i^{\alpha_i+\beta_i}=ab. $$ ### Conséquence Si l’on connaît le PGCD, on obtient le PPCM par $$ \operatorname{PPCM}(a,b)=\frac{a\times b}{\operatorname{PGCD}(a,b)}. $$ ### Exemple 1 (simple) Pour $a=24$, $b=36$ : - PGCD(24,36)=12 (par Euclide). - PPCM = $\dfrac{24\times36}{12}=72$. Vérification : multiples de 24 : 24,48,72,… ; de 36 : 36,72,… → le plus petit commun est 72. ### Exemple 2 (délicat) Pour $a=210$, $b=45$ : - Euclide : $210=45\times4+30$, $45=30\times1+15$, $30=15\times2+0$ → PGCD=15. - PPCM = $\dfrac{210\times45}{15}=630$. Vérification : $210\times45=9450$, $9450/15=630$. Multiples de 210 : 210,420,630,… ; de 45 : 45,90,135,180,225,270,315,360,405,450,495,540,585,630… → le plus petit commun est bien 630. ## Synthèse du chapitre - **PGCD** : plus grand entier divisant deux nombres. - **Algorithme des soustractions** : remplacer le plus grand par la différence jusqu’à égalité. - **Algorithme d’Euclide** : remplacer le couple $(a,b)$ par $(b, a\bmod b)$ jusqu’à reste nul. - **Relation PGCD‑PPCM** : $a\cdot b = \operatorname{PGCD}(a,b)\cdot\operatorname{PPCM}(a,b)$. - **PPCM** : plus petit entier multiple des deux nombres, obtenu par la formule ci‑dessus. - Les deux algorithmes donnent le même résultat ; Euclide est plus rapide (complexité logarithmique). ## Glossaire - **Diviseur** : entier $d$ tel qu’il existe $k$ avec $n = d\cdot k$. - **Multiple** : entier $m$ tel qu’il existe $k$ avec $m = n\cdot k$. - **PGCD** : Plus Grand Commun Diviseur. - **PPCM** : Plus Petit Commun Multiple. - **Algorithme des soustractions** : méthode basée sur la propriété $\operatorname{PGCD}(a,b)=\operatorname{PGCD}(a-b,b)$. - **Algorithme d’Euclide** : méthode basée sur la propriété $\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b, a\bmod b)$. - **Reste** : dans la division $a=bq+r$, l’entier $r$ avec $0\le r<b$. - **Factorisation première** : écriture d’un entier comme produit de puissances de nombres premiers. ## Exercices d'application corrigés ### Exercice 1 Calculer $\operatorname{PGCD}(84,30)$ par l’algorithme des soustractions et vérifier avec l’algorithme d’Euclide. **Corrigé** *Soustractions* : - $84>30$ → $84-30=54$ → $(54,30)$ - $54>30$ → $54-30=24$ → $(24,30)$ - $30>24$ → $30-24=6$ → $(24,6)$ - $24>6$ → $24-6=18$ → $(18,6)$ - $18>6$ → $18-6=12$ → $(12,6)$ - $12>6$ → $12-6=6$ → $(6,6)$ → PGCD = 6. *Euclide* : - $84 = 30\times2 + 24$ → $(30,24)$ - $30 = 24\times1 + 6$ → $(24,6)$ - $24 = 6\times4 + 0$ → PGCD = 6. Les deux méthodes donnent 6. ### Exercice 2 Déterminer le PGCD et le PPCM de $126$ et $84$. **Corrigé** PGCD (Euclide) : - $126 = 84\times1 + 42$ → $(84,42)$ - $84 = 42\times2 + 0$ → PGCD = 42. PPCM : $\operatorname{PPCM}= \dfrac{126\times84}{42}= \dfrac{10584}{42}=252$. Vérification : $126\times84 = 10584$, $42\times252 = 10584$. ### Exercice 3 Deux horloges sonnent respectivement toutes les 9 minutes et toutes les 12 minutes. Au bout de combien de minutes elles sonneront-elles en même temps pour la première fois après le départ ? **Corrigé** Le moment où elles coïncident est le PPCM de 9 et 12. PGCD(9,12) : - $12 = 9\times1 + 3$ → $(9,3)$ - $9 = 3\times3 + 0$ → PGCD = 3. PPCM = $\dfrac{9\times12}{3}=36$. Elles sonneront donc ensemble au bout de 36 minutes. ### Exercice 4 Montrer que si $\operatorname{PGCD}(a,b)=1$ alors $\operatorname{PPCM}(a,b)=ab$. **Corrigé** D’après la relation fondamentale : $ab = \operatorname{PGCD}(a,b)\times\operatorname{PPCM}(a,b)$. Si $\operatorname{PGCD}(a,b)=1$, alors $ab = 1\times\operatorname{PPCM}(a,b)$, donc $\operatorname{PPCM}(a,b)=ab$. ### Exercice 5 Un carreau de côté 18 cm doit être pavé avec des carreaux carrés identiques de côté entier le plus grand possible. Quelle est la longueur du côté du petit carreau et combien de tels carreaux sont nécessaires ? **Corrigé** Le côté du petit carreau doit être un diviseur de 18. Pour qu’il soit le plus grand possible, on prend le plus grand diviseur de 18, c’est‑à‑dire 18 lui‑même. Ainsi, le côté du petit carreau est $18$ cm. Le nombre de carreaux nécessaires est $$\frac{\text{surface du grand carreau}}{\text{surface d’un petit carreau}}= \frac{18\times18}{18\times18}=1.$$ Donc il suffit d’un seul carreau de $18$ cm de côté. ## Erreurs fréquentes 1. **Confondre PGCD et PPCM** : certains élèves donnent le plus petit commun diviseur au lieu du plus grand. Rappel : le PGCD divise les deux nombres, le PPCM est multiple des deux. 2. **Oublier la condition $b\neq0$ dans l’algorithme d’Euclide** : lorsqu’on arrive à $b=0$, le PGCD vaut le dernier $a$ non nul. Ne pas poursuivre la division. 3. **Utiliser la soustraction sans vérifier que les nombres restent positifs** : si on soustrait le plus grand du plus petit, on obtient un nombre négatif qui sort du domaine des entiers naturels. Toujours soustraire le plus petit du plus grand. 4. **Croire que le produit des deux nombres donne toujours le PPCM** : cela n’est vrai que lorsque les deux nombres sont premiers entre eux (PGCD=1). Dans le cas général, il faut diviser par le PGCD. 5. **Erreur de factorisation lors de la démonstration de la relation PGCD‑PPCM** : oublier que les exposants du PGCD sont les minima et ceux du PPCM les maxima, ce qui conduit à une somme d’exposants égale à celle du produit. 6. **Mauvaise lecture du reste dans l’algorithme d’Euclide** : confondre le quotient et le reste ; rappeler que $a = bq + r$ avec $0\le r<b$. --- Fin du cours.