Aller au contenu

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

\[x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}\]

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.

  1. Résoudre un système de congruences.
  2. 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.
  3. 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

\[n \equiv -1 \pmod{p_1^2}, \quad n \equiv -2 \pmod{p_2^2}, \quad \ldots, \quad n \equiv -k \pmod{p_k^2}.\]

É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

\[548 = 4 \times 137, \qquad 549 = 9 \times 61, \qquad 550 = 25 \times 22.\]

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

  1. Résoudre le système \(x \equiv 2 \pmod 3\), \(x \equiv 3 \pmod 5\), \(x \equiv 2 \pmod 7\). Indication : chercher d'abord \(x\) modulo \(15\) parmi \(2, 5, 8, 11, 14\).
  2. 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\). Indication : \(n - 1\) est un multiple de \(\operatorname{ppcm}(2, 3, 4, 5, 6) = 60\).
  3. Combien l'équation \(x^2 \equiv 1 \pmod{105}\) a-t-elle de solutions modulo \(105\) ? Indication : \(x^2 \equiv 1\) a exactement deux solutions modulo chacun des nombres premiers \(3\), \(5\) et \(7\).
  4. 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.
  5. 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. Indication : choisir \(k\) nombres premiers distincts \(p_1, \ldots, p_k\) et imposer \(x + i \equiv 0 \pmod{p_i}\).

Parcours suggéré

Un choix de problèmes de la shortlist, du plus accessible au plus difficile, où ce concept joue le premier rôle. La liste complète est plus bas.

Étape 1 — Premiers pas (1 ★)

La shortlist n'a pas de problème de ce niveau sur ce thème : les exercices d'échauffement en tiennent lieu.

Étape 2 — Consolidation (2 ★)

  • 2009 N1 ★★☆☆☆ · OIM P1 : Les membres d'un club s'envoient des cadeaux selon une règle de divisibilité : aucun cadeau ne revient à son expéditeur.
  • 2016 N3 ★★☆☆☆ · OIM P4 : Des valeurs consécutives de \(n^2 + n + 1\) dont aucune n'est première avec le produit des autres : combien en faut-il au minimum ?

Étape 3 — Approfondissement (3 ★)

  • 2010 N4 ★★★☆☆ : Quand \(ax^3 + bx\) est-il injectif modulo \(n\) ? Comparer cette propriété pour \(n = 51\), \(n = 2010\) et une infinité de \(n\).

Étape 4 — Défi (4 ★ – 5 ★)

  • 2014 N6 ★★★★☆ : Les multiples de \(a_1, \ldots, a_n\) découpent un segment : la somme des carrés des longueurs des morceaux est divisible par \(a_1\).
  • 2021 N8 ★★★★★ : Pour quels \(n\) un polynôme entier itéré \(m\) fois divise-t-il par deux, à chaque fois, le nombre de restes modulo \(n\) ?

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

La shortlist compte très peu de problèmes faciles sur ce thème : si le concept est nouveau pour vous, commencez par les exercices d'échauffement ci-dessus.

12 problèmes · difficulté moyenne : ★★★★★ (3,8) · dont 3 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 0 · 2 ★ : 2 · 3 ★ : 1 · 4 ★ : 6 · 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
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