Théorème des restes chinois¶
Domaine : Théorie des nombres · Niveau : intermédiaire · Prérequis : Divisibilité, PGCD, Congruences
L'idée¶
Théorème des restes chinois
Soient \(m_1, \ldots, m_k\) des entiers \(\geq 2\), deux à deux premiers entre eux, et \(a_1, \ldots, a_k\) des entiers quelconques. Le système
a des solutions, et elles forment une seule classe modulo \(M = m_1 m_2 \cdots m_k\).
Pourquoi. Posons \(M_i = \frac{M}{m_i}\). Comme \(M_i\) est premier avec \(m_i\), il a un inverse \(u_i\) modulo \(m_i\) (par Bézout). Le nombre \(x = a_1 M_1 u_1 + \cdots + a_k M_k u_k\) convient : modulo \(m_i\), tous les termes sont nuls sauf le \(i\)-ème, qui vaut \(a_i M_i u_i \equiv a_i\). Pour l'unicité, deux solutions ont une différence divisible par chaque \(m_i\), donc par leur produit \(M\).
Le théorème s'utilise dans trois directions.
- Résoudre un système de congruences.
- Construire un entier qui a des restes imposés modulo plusieurs nombres. C'est l'usage le plus fréquent en olympiade : on fabrique un \(n\) tel que \(n\), \(n + 1\), \(n + 2\), … aient chacun une propriété voulue.
- Découper un problème modulo \(n\) en problèmes modulo chaque puissance de premier \(p^\alpha\) qui divise \(n\). Une congruence modulo \(n\) équivaut aux congruences modulo chaque \(p^\alpha\), et le nombre de solutions modulo \(n\) est le produit des nombres de solutions modulo chaque \(p^\alpha\).
Si les modules ne sont pas premiers entre eux, le système \(x \equiv a \pmod m\), \(x \equiv b \pmod{m'}\) a une solution si et seulement si \(a \equiv b \pmod{\operatorname{pgcd}(m, m')}\), et elle est alors unique modulo \(\operatorname{ppcm}(m, m')\).
Exemple résolu¶
Problème
Montrer que pour tout entier \(k \geq 1\), il existe \(k\) entiers consécutifs dont chacun est divisible par le carré d'un nombre premier.
Étape 1 : choisir un module pour chaque entier. On prend \(k\) nombres premiers distincts \(p_1, p_2, \ldots, p_k\) (il y en a une infinité). On veut que \(n + i\) soit divisible par \(p_i^2\), pour \(i = 1, \ldots, k\).
Étape 2 : écrire le système. Cela s'écrit
Étape 3 : appliquer le théorème. Les modules \(p_1^2, \ldots, p_k^2\) sont deux à deux premiers entre eux, car les \(p_i\) sont distincts. Le système a donc une solution \(n\), que l'on peut choisir positive. Les entiers \(n + 1, \ldots, n + k\) conviennent.
Par exemple, pour \(k = 3\) avec \(p_1 = 2\), \(p_2 = 3\), \(p_3 = 5\), le plus petit \(n\) positif est \(547\), et l'on obtient
Le réflexe : pour construire un entier aux propriétés multiples, attribuer à chaque propriété son propre nombre premier, puis recoller.
Comment le reconnaître¶
- On demande de montrer qu'il existe un entier (ou des entiers consécutifs) avec plusieurs propriétés de divisibilité.
- On doit résoudre un système de congruences.
- Le module \(n\) est composé et le problème est plus simple modulo un premier ou une puissance de premier.
- On compte les solutions d'une congruence modulo un entier composé.
- Une fonction se comporte bien sur des entiers premiers entre eux : \(f(ab) = f(a) f(b)\).
Techniques classiques¶
| Situation | Technique |
|---|---|
| Système de congruences à modules premiers entre eux | Restes chinois ; construire la solution avec les \(\frac{M}{m_i}\) et leurs inverses |
| Modules non premiers entre eux | Vérifier la compatibilité modulo le PGCD, ou découper en puissances de premiers |
| \(k\) entiers consécutifs ayant une propriété | Un premier (ou une puissance de premier) par entier, puis recoller |
| Congruence modulo \(n\) composé | La résoudre modulo chaque \(p^\alpha\) divisant \(n\), puis recoller |
| Nombre de solutions modulo \(n\) | Produit des nombres de solutions modulo chaque \(p^\alpha\) |
| Éviter des classes « interdites » | Les combiner modulo des entiers premiers entre eux ; les proportions se multiplient |
Exercices d'échauffement¶
- Résoudre le système \(x \equiv 2 \pmod 3\), \(x \equiv 3 \pmod 5\), \(x \equiv 2 \pmod 7\).
- Trouver le plus petit entier \(n > 0\) qui a pour reste \(1\) dans la division par \(2\), \(3\), \(4\), \(5\) et \(6\), et qui est divisible par \(7\).
- Combien l'équation \(x^2 \equiv 1 \pmod{105}\) a-t-elle de solutions modulo \(105\) ?
- Montrer qu'il existe \(100\) entiers consécutifs dont aucun n'est une puissance d'un nombre premier. Indication : faire diviser chacun par deux premiers distincts.
- Montrer que pour tout \(k\), il existe \(k\) entiers consécutifs dont aucun n'est premier, de deux façons : avec \((k+1)! + 2, \ldots, (k+1)! + k + 1\), puis avec les restes chinois.
Restes chinois dans la shortlist¶
- 2016 N3 : on construit un ensemble de taille \(6\) en combinant des conditions modulo \(19\), \(7\) et \(3\).
- 2015 N7, solution 2 : on fixe \(f(m)\) modulo chaque premier « dangereux ».
- 2017 N7, solution 1 : on recolle des polynômes construits pour chaque puissance de premier, grâce à une relation de Bézout.
- 2021 N8 : pour \(n = ab\) avec \(\operatorname{pgcd}(a, b) = 1\), la quantité étudiée est le produit de celles pour \(a\) et pour \(b\).
- 2025 N6, partie (b) : des classes interdites modulo des entiers premiers entre eux se combinent.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 5 (M. Aassila), p. 152 (entiers inversibles modulo \(n\)), p. 153 à 156 (théorème des restes chinois, deux énoncés et preuves), puis exemples et exercices jusqu'à p. 166, p. 39 (une première version au chapitre sur le PGCD), p. 74 à 76 (systèmes congruentiels, exemples).
Problèmes de la shortlist¶
13 problèmes · difficulté moyenne : ★★★★★ (3,8) · dont 3 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 0 · 2 ★ : 2 · 3 ★ : 1 · 4 ★ : 7 · 5 ★ : 3
| Problème | Difficulté | Concepts |
|---|---|---|
| 2016 N3 · OIM P4 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler |
| 2009 N1 · OIM P1 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Graphes : degrés, chemins, arbres |
| 2010 N4 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs |
| 2025 N6 | ★★★★☆ | Récurrence et constructions récursives · Divisibilité, PGCD et algorithme d'Euclide |
| 2019 N7 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Ordre d'un élément et racines primitives |
| 2017 N7 · OIM P6 | ★★★★☆ | Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler · Divisibilité, PGCD et algorithme d'Euclide |
| 2015 N7 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Récurrence et constructions récursives |
| 2014 N6 | ★★★★☆ | Double comptage · Congruences, théorèmes de Fermat et d'Euler · Polynômes à coefficients entiers |
| 2012 N6 | ★★★★☆ | Ordre d'un élément et racines primitives · Résidus quadratiques · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2006 N7 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Récurrence et constructions récursives |
| 2023 N8 | ★★★★★ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs |
| 2021 N8 | ★★★★★ | Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler |
| 2010 C7 | ★★★★★ | Graphes : degrés, chemins, arbres · Récurrence et constructions récursives |