Congruences, théorèmes de Fermat et d'Euler¶
Domaine : Théorie des nombres · Niveau : débutant · Prérequis : Divisibilité, PGCD
L'idée¶
On écrit \(a \equiv b \pmod n\) quand \(n\) divise \(a - b\), c'est-à-dire quand \(a\) et \(b\) ont le même reste dans la division par \(n\). Les congruences se additionnent, se multiplient et s'élèvent à une puissance comme des égalités :
Attention à la division. On ne peut simplifier par \(c\) dans \(ac \equiv bc \pmod n\) que si \(\operatorname{pgcd}(c, n) = 1\). Par exemple \(2 \cdot 3 \equiv 2 \cdot 1 \pmod 4\), mais \(3 \not\equiv 1 \pmod 4\).
Les congruences servent surtout à deux choses : montrer qu'une équation n'a pas de solution (en regardant les restes possibles des deux membres), et calculer des puissances modulo \(n\).
Restes à connaître¶
| Puissances | Restes possibles |
|---|---|
| Carrés modulo \(3\) | \(0, 1\) |
| Carrés modulo \(4\) | \(0, 1\) |
| Carrés modulo \(8\) | \(0, 1, 4\) (et \(1\) pour un impair) |
| Carrés modulo \(5\) | \(0, 1, 4\) |
| Cubes modulo \(7\) | \(0, 1, 6\) |
| Cubes modulo \(9\) | \(0, 1, 8\) |
| Puissances quatrièmes modulo \(16\) | \(0, 1\) |
Les trois théorèmes¶
| Théorème | Énoncé |
|---|---|
| Petit théorème de Fermat | Si \(p\) est premier, \(a^p \equiv a \pmod p\) ; si de plus \(p \nmid a\), alors \(a^{p-1} \equiv 1 \pmod p\) |
| Théorème d'Euler | Si \(\operatorname{pgcd}(a, n) = 1\), alors \(a^{\varphi(n)} \equiv 1 \pmod n\), où \(\varphi(n)\) est le nombre d'entiers de \(1\) à \(n\) premiers avec \(n\) |
| Théorème de Wilson | \(p\) est premier si et seulement si \((p - 1)! \equiv -1 \pmod p\) |
Pourquoi Fermat. Si \(p \nmid a\), les nombres \(a, 2a, \ldots, (p-1)a\) ont des restes non nuls et deux à deux distincts modulo \(p\) (car on peut simplifier par \(a\)). Ce sont donc les restes \(1, 2, \ldots, p - 1\) dans un autre ordre. En multipliant : \(a^{p-1}(p-1)! \equiv (p-1)! \pmod p\), et l'on simplifie par \((p - 1)!\), premier avec \(p\).
Conséquence pratique : modulo un premier \(p\), les exposants se réduisent modulo \(p - 1\) (pour \(a\) non divisible par \(p\)). Modulo \(n\), ils se réduisent modulo \(\varphi(n)\) pour \(a\) premier avec \(n\).
Exemple résolu¶
Problème
Soit \(p\) un nombre premier différent de \(2\), \(3\) et \(5\). Montrer que \(p\) divise le nombre \(11\ldots1\) formé de \(p - 1\) chiffres \(1\).
Étape 1 : écrire le nombre avec une puissance. Le nombre formé de \(k\) chiffres \(1\) vaut \(1 + 10 + \cdots + 10^{k-1} = \frac{10^k - 1}{9}\). Ici \(k = p - 1\) :
Étape 2 : appliquer Fermat. Comme \(p \neq 2, 5\), \(p\) ne divise pas \(10\), donc \(10^{p-1} \equiv 1 \pmod p\). Ainsi \(p\) divise \(9N\).
Étape 3 : simplifier par \(9\), ce qui est permis. Comme \(p \neq 3\), \(p\) est premier avec \(9\). Par le lemme de Gauss, \(p\) divise \(N\).
Les trois exclusions de l'énoncé ont chacune un rôle : \(2\) et \(5\) pour appliquer Fermat à \(10\), et \(3\) pour pouvoir simplifier par \(9\). Pour \(p = 3\), d'ailleurs, \(N = 11\) n'est pas divisible par \(3\).
Comment le reconnaître¶
- On veut montrer qu'une équation en entiers n'a pas de solution, ou qu'une expression n'est jamais un carré, un cube.
- Des puissances avec un exposant variable : \(2^n\), \(a^{p-1}\), \(10^k\).
- Un nombre premier \(p\) et des exposants liés à \(p - 1\), ou une factorielle \((p - 1)!\).
- On cherche les derniers chiffres d'un nombre, ou son reste par un entier donné.
- Une expression doit être divisible par un entier fixé pour tout \(n\).
Techniques classiques¶
| Situation | Technique |
|---|---|
| Équation sans solution | Réduire modulo un petit entier bien choisi : \(3\), \(4\), \(8\), \(9\), \(7\), \(16\) |
| Choisir le module | Celui qui rend les puissances présentes très contraintes (carrés : \(4\) ou \(8\) ; cubes : \(7\) ou \(9\)) |
| Calculer \(a^k \bmod n\) | Fermat ou Euler pour réduire l'exposant, ou repérer le cycle des puissances |
| Simplifier une congruence | Seulement par un nombre premier avec le module |
| Une condition \(d \mid E\) | Travailler modulo \(d\) et y remplacer une variable par son expression (par exemple \(b \equiv -a^2 - 3\)) |
| \((p - 1)!\) ou produit de tous les restes | Théorème de Wilson |
| Plusieurs modules premiers entre eux | Combiner les congruences avec le théorème des restes chinois |
Exercices d'échauffement¶
- Montrer que \(n^3 - n\) est divisible par \(6\) pour tout entier \(n\).
- Montrer qu'un entier de la forme \(8k + 7\) n'est pas une somme de trois carrés.
- Quels sont les deux derniers chiffres de \(3^{100}\) ?
- Montrer que \(7\) divise \(3^{2n+1} + 2^{n+2}\) pour tout entier \(n \geq 0\).
- Soit \(p\) un nombre premier. Montrer que \((p - 2)! \equiv 1 \pmod p\).
Congruences dans la shortlist¶
- 2017 N1 : un carré n'est jamais \(\equiv -1 \pmod 3\) ; dès qu'un terme est \(\equiv -1\), la suite croît pour toujours.
- 2023 N2 : modulo \(4\), \(2^{a-2} - 1\) n'est pas un carré pour \(a \geq 4\).
- 2017 N2 : par le petit théorème de Fermat, \(10^{(p-1)/2} \equiv \pm 1 \pmod p\).
- 2019 N3, solution 1 : par le théorème d'Euler, \(t\) divise \(2^{\varphi(t)} - 1\) pour \(t\) impair.
- 2021 N1 : modulo \(a^2 + b + 3\), on remplace \(b\) par \(-a^2 - 3\).
Pour approfondir : Objectif Olympiades de Mathématiques, tome 5 (M. Aassila), p. 7 à 10 (premières propriétés, critères de divisibilité), p. 111 à 113 (congruences, classes de restes, carrés modulo \(4\) et \(8\)), p. 113 à 130 (exemples et exercices), p. 131 à 137 (petit théorème de Fermat), p. 138 à 144 (théorème d'Euler ; théorème d'Erdős-Ginzburg-Ziv p. 138), p. 145 à 151 (théorème de Wilson).
Problèmes de la shortlist¶
81 problèmes · difficulté moyenne : ★★★★★ (2,8) · dont 14 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 15 · 2 ★ : 16 · 3 ★ : 28 · 4 ★ : 17 · 5 ★ : 5
| Problème | Difficulté | Concepts |
|---|---|---|
| 2025 N1 | ★☆☆☆☆ | Principe des tiroirs |
| 2024 A1 · OIM P1 | ★☆☆☆☆ | Partie entière et majorations · Récurrence et constructions récursives |
| 2024 N1 | ★☆☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal |
| 2024 C2 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2024 N2 | ★☆☆☆☆ | Principe extrémal |
| 2023 N2 | ★☆☆☆☆ | Équations diophantiennes : factorisation et encadrement · Valuations p-adiques et lemme LTE |
| 2022 N2 | ★☆☆☆☆ | - |
| 2021 N1 | ★☆☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Équations diophantiennes : factorisation et encadrement |
| 2020 N1 | ★☆☆☆☆ | - |
| 2018 N2 | ★☆☆☆☆ | - |
| 2017 N1 · OIM P1 | ★☆☆☆☆ | Principe extrémal |
| 2017 N2 | ★☆☆☆☆ | Jeux et stratégies gagnantes |
| 2016 N2 | ★☆☆☆☆ | Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs |
| 2015 N1 | ★☆☆☆☆ | Valuations p-adiques et lemme LTE · Descente infinie et Vieta jumping |
| 2013 N2 · OIM P1 | ★☆☆☆☆ | Récurrence et constructions récursives · Sommes, télescopage et transformation d'Abel |
| 2025 N3 · OIM P4 | ★★☆☆☆ | Valuations p-adiques et lemme LTE · Invariants et monovariants · Descente infinie et Vieta jumping |
| 2024 N3 | ★★☆☆☆ | Valuations p-adiques et lemme LTE |
| 2022 N3 | ★★☆☆☆ | - |
| 2022 C4 | ★★☆☆☆ | Invariants et monovariants · Récurrence et constructions récursives · Polynômes à coefficients entiers |
| 2022 N4 · OIM P5 | ★★☆☆☆ | Équations diophantiennes : factorisation et encadrement · Valuations p-adiques et lemme LTE · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2021 N4 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2019 N3 | ★★☆☆☆ | Principe des tiroirs |
| 2017 N3 | ★★☆☆☆ | Principe des tiroirs |
| 2016 N3 · OIM P4 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Théorème des restes chinois |
| 2015 N3 | ★★☆☆☆ | Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide |
| 2014 N1 | ★★☆☆☆ | Récurrence et constructions récursives · Principe extrémal |
| 2012 A2 | ★★☆☆☆ | Invariants et monovariants |
| 2012 N2 | ★★☆☆☆ | Équations diophantiennes : factorisation et encadrement · Valuations p-adiques et lemme LTE |
| 2008 N1 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2007 N1 | ★★☆☆☆ | Équations diophantiennes : factorisation et encadrement |
| 2006 N2 | ★★☆☆☆ | Ordre d'un élément et racines primitives |
| 2024 N4 · OIM P2 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Valuations p-adiques et lemme LTE |
| 2024 N5 | ★★★☆☆ | Partie entière et majorations · Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide |
| 2022 N5 | ★★★☆☆ | Double comptage |
| 2021 N5 | ★★★☆☆ | AM-GM et moyennes · Valuations p-adiques et lemme LTE |
| 2020 N5 | ★★★☆☆ | Principe extrémal · Valuations p-adiques et lemme LTE |
| 2019 N5 | ★★★☆☆ | Valuations p-adiques et lemme LTE |
| 2017 N5 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Ordre d'un élément et racines primitives |
| 2015 N5 · OIM P2 | ★★★☆☆ | Équations diophantiennes : factorisation et encadrement · Valuations p-adiques et lemme LTE |
| 2014 A4 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Récurrence et constructions récursives |
| 2014 N4 | ★★★☆☆ | Partie entière et majorations · Valuations p-adiques et lemme LTE |
| 2014 N5 | ★★★☆☆ | Valuations p-adiques et lemme LTE · Équations diophantiennes : factorisation et encadrement |
| 2013 N4 | ★★★☆☆ | Valuations p-adiques et lemme LTE · Équations diophantiennes : factorisation et encadrement |
| 2013 A5 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Double comptage |
| 2012 N5 | ★★★☆☆ | Polynômes à coefficients entiers · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2011 N3 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2011 N4 | ★★★☆☆ | Valuations p-adiques et lemme LTE |
| 2010 N3 | ★★★☆☆ | Descente infinie et Vieta jumping |
| 2010 N4 | ★★★☆☆ | Principe des tiroirs · Théorème des restes chinois |
| 2009 N4 | ★★★☆☆ | Descente infinie et Vieta jumping · Équations diophantiennes : factorisation et encadrement |
| 2008 N2 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2008 A4 | ★★★☆☆ | Suites et récurrences |
| 2008 N4 | ★★★☆☆ | Valuations p-adiques et lemme LTE |
| 2008 N6 · OIM P3 | ★★★☆☆ | Résidus quadratiques |
| 2007 N3 | ★★★☆☆ | Principe des tiroirs · Double comptage |
| 2007 N4 | ★★★☆☆ | Valuations p-adiques et lemme LTE |
| 2007 N5 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2007 N6 · OIM P5 | ★★★☆☆ | Descente infinie et Vieta jumping |
| 2006 N5 | ★★★☆☆ | Ordre d'un élément et racines primitives |
| 2025 N7 · OIM P3 | ★★★★☆ | Ordre d'un élément et racines primitives · Valuations p-adiques et lemme LTE |
| 2024 N6 | ★★★★☆ | Résidus quadratiques · Principe des tiroirs · Double comptage |
| 2023 N6 | ★★★★☆ | Suites et récurrences |
| 2022 A7 | ★★★★☆ | - |
| 2022 N7 · OIM P3 | ★★★★☆ | Polynômes : racines, relations de Viète, factorisation · Récurrence et constructions récursives |
| 2021 N6 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide · Récurrence et constructions récursives |
| 2019 N7 | ★★★★☆ | Théorème des restes chinois · Ordre d'un élément et racines primitives |
| 2017 N7 · OIM P6 | ★★★★☆ | Polynômes à coefficients entiers · Théorème des restes chinois · Divisibilité, PGCD et algorithme d'Euclide |
| 2015 N7 | ★★★★☆ | Théorème des restes chinois · Récurrence et constructions récursives |
| 2014 N6 | ★★★★☆ | Théorème des restes chinois · Double comptage · Polynômes à coefficients entiers |
| 2014 N7 | ★★★★☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Suites et récurrences · Valuations p-adiques et lemme LTE |
| 2012 N7 · OIM P6 | ★★★★☆ | Récurrence et constructions récursives |
| 2011 N7 | ★★★★☆ | Valuations p-adiques et lemme LTE |
| 2009 N5 | ★★★★☆ | Polynômes à coefficients entiers · Double comptage |
| 2009 N6 | ★★★★☆ | Polynômes à coefficients entiers · Suites et récurrences |
| 2006 N6 | ★★★★☆ | Équations diophantiennes : factorisation et encadrement · Convexité, inégalité de Jensen, lissage |
| 2006 N7 | ★★★★☆ | Théorème des restes chinois · Récurrence et constructions récursives |
| 2025 N8 | ★★★★★ | Équations diophantiennes : factorisation et encadrement · Résidus quadratiques · Divisibilité, PGCD et algorithme d'Euclide |
| 2022 N8 | ★★★★★ | Principe extrémal · Principe des tiroirs · Résidus quadratiques |
| 2021 N8 | ★★★★★ | Théorème des restes chinois · Polynômes à coefficients entiers |
| 2016 N8 | ★★★★★ | Principe des tiroirs · Polynômes à coefficients entiers · Polynômes : racines, relations de Viète, factorisation · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2015 N8 | ★★★★★ | Divisibilité, PGCD et algorithme d'Euclide · Principe des tiroirs |