Divisibilité, PGCD et algorithme d'Euclide¶
Domaine : Théorie des nombres · Niveau : débutant · Prérequis : aucun
L'idée¶
On dit que \(a\) divise \(b\), et l'on écrit \(a \mid b\), s'il existe un entier \(k\) tel que \(b = ka\). Le PGCD de \(a\) et \(b\) est le plus grand entier qui divise les deux ; ils sont premiers entre eux si leur PGCD vaut \(1\).
Le fait le plus utile est presque évident :
On s'en sert pour éliminer une variable : si \(d\) divise deux expressions en \(n\), on cherche une combinaison où \(n\) disparaît. Par exemple, \(d = \operatorname{pgcd}(n^2 + 1, n + 1)\) divise \((n^2 + 1) - (n - 1)(n + 1) = 2\), donc vaut \(1\) ou \(2\).
Les théorèmes de base¶
| Résultat | Énoncé |
|---|---|
| Division euclidienne | Pour \(b > 0\), il existe un unique couple \((q, r)\) avec \(a = bq + r\) et \(0 \leq r < b\) |
| Algorithme d'Euclide | \(\operatorname{pgcd}(a, b) = \operatorname{pgcd}(b, r)\) où \(r\) est le reste de \(a\) par \(b\) ; on itère jusqu'à un reste nul |
| Bézout | \(\operatorname{pgcd}(a, b) = 1\) si et seulement s'il existe des entiers \(u, v\) avec \(au + bv = 1\) ; plus généralement, le PGCD est la plus petite combinaison \(au + bv\) strictement positive |
| Gauss | Si \(a \mid bc\) et \(\operatorname{pgcd}(a, b) = 1\), alors \(a \mid c\) |
| Produit | Si \(a \mid c\), \(b \mid c\) et \(\operatorname{pgcd}(a, b) = 1\), alors \(ab \mid c\) |
| PGCD et PPCM | \(\operatorname{pgcd}(a, b) \times \operatorname{ppcm}(a, b) = ab\) pour \(a, b > 0\) |
| Taille | Si \(a \mid b\) et \(b \neq 0\), alors \(\lvert a \rvert \leq \lvert b \rvert\) |
Le dernier point est souvent décisif : un entier non nul n'a que des diviseurs plus petits que lui. En particulier, un entier fixé divisible par des nombres arbitrairement grands est nul.
Exemple résolu¶
Problème
Soient \(a \geq 2\), \(m\) et \(n\) des entiers strictement positifs. Montrer que \(\operatorname{pgcd}(a^m - 1, a^n - 1) = a^{\operatorname{pgcd}(m, n)} - 1\).
Étape 1 : une étape d'Euclide. Supposons \(m > n\). On élimine la plus grande puissance par une combinaison :
Tout diviseur commun de \(a^m - 1\) et \(a^n - 1\) divise donc \(a^{m-n} - 1\), et réciproquement. Ainsi
Étape 2 : reconnaître l'algorithme. Sur les exposants, on a remplacé \((m, n)\) par \((m - n, n)\) : c'est exactement l'algorithme d'Euclide par soustractions, qui ne change pas \(\operatorname{pgcd}(m, n)\).
Étape 3 : conclure. On répète jusqu'à ce que les deux exposants soient égaux, à \(g = \operatorname{pgcd}(m, n)\). Le PGCD cherché vaut alors \(\operatorname{pgcd}(a^g - 1, a^g - 1) = a^g - 1\).
Par exemple, \(\operatorname{pgcd}(2^{12} - 1, 2^{18} - 1) = 2^6 - 1 = 63\).
Le réflexe : pour un PGCD d'expressions, chercher la combinaison qui fait baisser le degré ou l'exposant, comme dans une division euclidienne.
Comment le reconnaître¶
- L'énoncé contient « \(a\) divise \(b\) », une fraction à rendre irréductible, ou un PGCD d'expressions en \(n\).
- On cherche les \(n\) tels qu'une expression en divise une autre.
- On manipule la liste des diviseurs d'un entier.
- Un produit de facteurs premiers entre eux vaut une puissance, ou est divisible par un nombre donné.
- Une divisibilité donne une borne : le diviseur est plus petit que le multiple.
Techniques classiques¶
| Situation | Technique |
|---|---|
| PGCD de deux expressions en \(n\) | Combinaison qui élimine \(n\), ou algorithme d'Euclide sur les expressions |
| \(f(n)\) divisible par \(g(n)\) (polynômes) | Retrancher un multiple de \(g(n)\) pour faire baisser le degré, jusqu'à une constante |
| \(a \mid b\) avec \(b \neq 0\) | En déduire \(\lvert a \rvert \leq \lvert b \rvert\) |
| Ajouter le diviseur au dividende | \(a \mid b\) si et seulement si \(a \mid b + ka\) : choisir \(k\) pour factoriser |
| Diviseurs d'un entier \(n\) | Les apparier : \(d \leftrightarrow \frac{n}{d}\) |
| Termes ayant un facteur commun | Diviser par le PGCD pour se ramener à des nombres premiers entre eux |
| \(ab\) est un carré et \(\operatorname{pgcd}(a, b) = 1\) (\(a, b > 0\)) | \(a\) et \(b\) sont des carrés |
| \(a^m - 1\) et \(a^n - 1\) | Leur PGCD vaut \(a^{\operatorname{pgcd}(m, n)} - 1\) |
Exercices d'échauffement¶
- Montrer que la fraction \(\frac{21n + 4}{14n + 3}\) est irréductible pour tout entier \(n\).
- Trouver tous les entiers \(n \geq 1\) tels que \(n + 1\) divise \(n^2 + 1\).
- Montrer que \(\operatorname{pgcd}(n! + 1, (n + 1)! + 1) = 1\) pour tout \(n \geq 1\).
- Trouver tous les couples d'entiers \((x, y)\) tels que \(7x + 5y = 1\).
- Soient \(a, b > 0\) premiers entre eux tels que \(ab\) soit un carré parfait. Montrer que \(a\) et \(b\) sont des carrés parfaits.
Divisibilité dans la shortlist¶
- 2016 N3 : des identités comme \((2n + 7)P(n) - (2n - 1)P(n + 2) = 14\) bornent \(\operatorname{pgcd}(P(n), P(n + k))\).
- 2016 N4 : on ajoute le diviseur au dividende, puis on simplifie par une puissance de \(n\).
- 2019 N2 : \(a^2\) divise \(b^3 + c^3\), donc \(b^3 + c^3 \geq a^2\), ce qui borne les variables.
- 2025 N2 : \(\operatorname{pgcd}(i, j)\) et \(\operatorname{pgcd}(i + 1, j)\) sont premiers entre eux et divisent \(j\), donc leur produit divise \(j\).
- 2021 N4 : \(\operatorname{pgcd}(a - b, b) = \operatorname{pgcd}(a + b, b) = 1\).
Pour approfondir : Objectif Olympiades de Mathématiques, tome 5 (M. Aassila), p. 5 et 6 (divisibilité, division euclidienne, numération), p. 29 et 30 (PGCD, PPCM, algorithme d'Euclide), p. 31 à 34 (nombres premiers entre eux, Bézout p. 32, Gauss p. 33, PGCD et PPCM p. 34), p. 36 (PGCD de \(a^m - b^m\) et \(a^n - b^n\)), p. 37 (l'équation \(ax + by = c\)), puis exemples et exercices jusqu'à p. 56.
Problèmes de la shortlist¶
72 problèmes · difficulté moyenne : ★★★★★ (2,8) · dont 10 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 15 · 2 ★ : 15 · 3 ★ : 19 · 4 ★ : 16 · 5 ★ : 7
| Problème | Difficulté | Concepts |
|---|---|---|
| 2025 N2 | ★☆☆☆☆ | - |
| 2024 N1 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler · Principe extrémal |
| 2023 N1 · OIM P1 | ★☆☆☆☆ | Récurrence et constructions récursives · Valuations p-adiques et lemme LTE |
| 2022 N1 | ★☆☆☆☆ | Équations diophantiennes : factorisation et encadrement |
| 2021 C1 | ★☆☆☆☆ | Principe des tiroirs |
| 2021 N1 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler · Équations diophantiennes : factorisation et encadrement |
| 2021 A2 | ★☆☆☆☆ | Partie entière et majorations |
| 2019 N2 | ★☆☆☆☆ | Équations diophantiennes : factorisation et encadrement |
| 2016 C2 | ★☆☆☆☆ | Principe extrémal · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs |
| 2015 A2 | ★☆☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2015 N2 | ★☆☆☆☆ | - |
| 2013 N1 | ★☆☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2012 N1 | ★☆☆☆☆ | - |
| 2011 A1 · OIM P1 | ★☆☆☆☆ | Équations diophantiennes : factorisation et encadrement |
| 2010 N1 | ★☆☆☆☆ | Sommes, télescopage et transformation d'Abel |
| 2025 N4 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2023 N4 | ★★☆☆☆ | Suites et récurrences |
| 2021 N3 | ★★☆☆☆ | Équations diophantiennes : factorisation et encadrement |
| 2021 N4 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2020 N3 · OIM P5 | ★★☆☆☆ | Principe extrémal · Valuations p-adiques et lemme LTE |
| 2019 N4 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe des tiroirs |
| 2016 N3 · OIM P4 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois |
| 2016 N4 | ★★☆☆☆ | Équations diophantiennes : factorisation et encadrement |
| 2015 C3 | ★★☆☆☆ | - |
| 2015 N3 | ★★☆☆☆ | Valuations p-adiques et lemme LTE · Congruences, théorèmes de Fermat et d'Euler |
| 2015 N4 | ★★☆☆☆ | Invariants et monovariants · Suites et récurrences |
| 2013 N3 | ★★☆☆☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Principe extrémal |
| 2012 N3 | ★★☆☆☆ | Bijections et dénombrement |
| 2009 N1 · OIM P1 | ★★☆☆☆ | Théorème des restes chinois · Graphes : degrés, chemins, arbres |
| 2008 N1 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2025 N5 | ★★★☆☆ | Invariants et monovariants · Valuations p-adiques et lemme LTE |
| 2024 N4 · OIM P2 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE |
| 2024 N5 | ★★★☆☆ | Partie entière et majorations · Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE |
| 2023 N5 | ★★★☆☆ | Suites et récurrences · Principe extrémal |
| 2022 C6 | ★★★☆☆ | Récurrence et constructions récursives · Invariants et monovariants |
| 2020 N4 | ★★★☆☆ | Ordre d'un élément et racines primitives · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2020 C5 | ★★★☆☆ | Principe extrémal |
| 2018 N4 · OIM P5 | ★★★☆☆ | Valuations p-adiques et lemme LTE |
| 2017 N5 | ★★★☆☆ | Ordre d'un élément et racines primitives · Congruences, théorèmes de Fermat et d'Euler |
| 2013 N5 | ★★★☆☆ | Jeux et stratégies gagnantes · Principe extrémal |
| 2011 N3 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2011 N5 · OIM P5 | ★★★☆☆ | Principe extrémal |
| 2010 N2 | ★★★☆☆ | Équations diophantiennes : factorisation et encadrement · Ordre d'un élément et racines primitives |
| 2009 N3 | ★★★☆☆ | Valuations p-adiques et lemme LTE |
| 2008 N2 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2008 C3 | ★★★☆☆ | Principe des tiroirs · Principe extrémal |
| 2008 N3 | ★★★☆☆ | Récurrence et constructions récursives |
| 2007 C5 | ★★★☆☆ | Coloriages et pavages |
| 2006 N4 · OIM P5 | ★★★☆☆ | Polynômes à coefficients entiers |
| 2025 A6 | ★★★★☆ | Principe des tiroirs · Suites et récurrences |
| 2025 N6 | ★★★★☆ | Récurrence et constructions récursives · Théorème des restes chinois |
| 2024 A6 | ★★★★☆ | Invariants et monovariants |
| 2023 N7 | ★★★★☆ | Équations diophantiennes : factorisation et encadrement |
| 2021 N6 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Récurrence et constructions récursives |
| 2021 N7 | ★★★★☆ | Principe extrémal · Suites et récurrences |
| 2020 A6 | ★★★★☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal |
| 2018 C6 | ★★★★☆ | Invariants et monovariants |
| 2018 N6 | ★★★★☆ | Principe des tiroirs |
| 2017 N6 | ★★★★☆ | Descente infinie et Vieta jumping |
| 2017 N7 · OIM P6 | ★★★★☆ | Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois |
| 2016 N6 | ★★★★☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2015 A5 | ★★★★☆ | Sommes, télescopage et transformation d'Abel · Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2015 N6 | ★★★★☆ | Principe des tiroirs |
| 2011 N6 | ★★★★☆ | Ordre d'un élément et racines primitives · Polynômes à coefficients entiers |
| 2008 A6 | ★★★★☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2025 N8 | ★★★★★ | Équations diophantiennes : factorisation et encadrement · Congruences, théorèmes de Fermat et d'Euler · Résidus quadratiques |
| 2024 N7 | ★★★★★ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Valuations p-adiques et lemme LTE · Graphes : degrés, chemins, arbres |
| 2024 A8 | ★★★★★ | Principe extrémal · Suites et récurrences |
| 2023 N8 | ★★★★★ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · Théorème des restes chinois |
| 2018 N7 | ★★★★★ | Valuations p-adiques et lemme LTE |
| 2017 N8 | ★★★★★ | Résidus quadratiques · Partie entière et majorations |
| 2015 N8 | ★★★★★ | Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs |