Rédigé et vérifié par un professeur diplômé de l’École Polytechnique, avec le niveau d’exigence attendu en classe préparatoire. Découvrir le professeur

En arithmétique, restreindre les solutions à \(\mathbb{Z}\) change radicalement la nature d’une équation. Les équations diophantiennes — nommées d’après Diophante d’Alexandrie (IIIe siècle) — sont au cœur du programme d’arithmétique en CPGE : elles relient divisibilité, PGCD et théorème de Bézout en un outil puissant. Ce cours couvre le théorème d’existence, la description complète des solutions, la méthode de résolution par algorithme d’Euclide et 8 exercices corrigés de difficulté croissante.

📚 Tout le cours « Équations & Inéquations »

I. Définition et contexte

A. Définition formelle

Définition — Équation diophantienne

Soit \(P \in \mathbb{Z}[X_1, \ldots, X_n]\) un polynôme à coefficients entiers. L’équation \(P(x_1, \ldots, x_n) = 0\) est dite diophantienne lorsqu’on cherche ses solutions dans \(\mathbb{Z}^n\) (ou dans \(\mathbb{N}^n\)).

Le terme rend hommage à Diophante d’Alexandrie, mathématicien grec du IIIe siècle, auteur des Arithmetica — le premier traité consacré à la résolution d’équations en nombres entiers.

En CPGE, le programme se concentre sur le cas linéaire, qui constitue la brique de base de l’arithmétique des entiers :

Équation diophantienne linéaire (programme CPGE)

Soient \(a, b, c \in \mathbb{Z}\) avec \((a, b) \neq (0, 0)\). On appelle équation diophantienne linéaire l’équation :

\(ax + by = c, \quad (x, y) \in \mathbb{Z}^2\)

Programme CPGE : Les équations diophantiennes linéaires figurent au programme d’arithmétique de toutes les filières Maths Sup (MPSI, PCSI, PTSI, MP2I). En Maths Spé, le sujet est approfondi en MP/MP*.

B. Exemples fondamentaux

Le spectre des équations diophantiennes est vaste. Voici les cas classiques :

Exemples d'équations diophantiennes
Équation Type Statut
\(3x + 5y = 1\) Linéaire Résolue (théorème de Bézout)
\(x^2 + y^2 = z^2\) Quadratique Résolue (triplets pythagoriciens)
\(x^n + y^n = z^n\), \(n \geq 3\) Puissance \(n\) Pas de solution non triviale (Wiles, 1995)
\(x^2 – ny^2 = 1\) Équation de Pell-Fermat Infinité de solutions pour \(n\) non carré parfait

C. Lien avec l’arithmétique dans \(\mathbb{Z}\)

L’étude de l’équation \(ax + by = c\) dans \(\mathbb{Z}^2\) repose entièrement sur deux outils du chapitre d’arithmétique :

  • Le PGCD et l’algorithme d’Euclide pour calculer \(\mathrm{pgcd}(a, b)\).
  • Le théorème de Bézout : \(\mathrm{pgcd}(a, b) = d \;\Longrightarrow\; \exists\, u, v \in \mathbb{Z},\; au + bv = d\).

Contrairement à une équation à deux inconnues dans \(\mathbb{R}\) (où la droite \(ax + by = c\) contient une infinité de points), la contrainte \((x, y) \in \mathbb{Z}^2\) ne retient que les points à coordonnées entières — un ensemble discret, éventuellement vide.

II. Théorème d’existence et structure des solutions

La question se décompose en deux temps : quand l’équation admet-elle des solutions ? Et si oui, combien y en a-t-il, et comment les décrire toutes ?

A. Condition nécessaire et suffisante

Théorème (Existence des solutions) ⋆

Soient \(a, b \in \mathbb{Z}\) non tous deux nuls, et \(c \in \mathbb{Z}\). Posons \(d = \mathrm{pgcd}(a, b)\).

L’équation \(ax + by = c\) admet des solutions \((x, y) \in \mathbb{Z}^2\) si et seulement si \(d \mid c\).

Ce théorème est fondamental : il ramène l’existence de solutions à un simple test de divisibilité. Pas besoin de chercher une solution — il suffit de vérifier si \(\mathrm{pgcd}(a, b)\) divise \(c\).

B. Démonstration ⋆

\(\Longrightarrow\) (Condition nécessaire)

Supposons que \((x_0, y_0) \in \mathbb{Z}^2\) soit solution : \(ax_0 + by_0 = c\).

Or \(d \mid a\) et \(d \mid b\), donc \(d \mid (ax_0 + by_0) = c\). ∎

\(\Longleftarrow\) (Condition suffisante)

Supposons \(d \mid c\). Par le théorème de Bézout, il existe \(u, v \in \mathbb{Z}\) tels que \(au + bv = d\).

Posons \(q = \displaystyle\frac{c}{d} \in \mathbb{Z}\). Alors :

\(a(uq) + b(vq) = dq = c\)

Le couple \((uq, vq)\) est donc solution. ∎

Conséquence immédiate : si \(\mathrm{pgcd}(a, b)\) ne divise pas \(c\), l’équation n’a aucune solution. Par exemple, \(6x + 10y = 11\) n’a aucune solution dans \(\mathbb{Z}^2\) car \(\mathrm{pgcd}(6, 10) = 2\) et \(2\) ne divise pas \(11\). Vérifie toujours cette condition avant de te lancer dans la résolution.

C. Description complète de l’ensemble des solutions

Lorsque des solutions existent, elles forment une famille paramétrée par un unique entier \(k \in \mathbb{Z}\).

Théorème (Structure des solutions) ⋆

Soient \(a, b \in \mathbb{Z}^*\), \(c \in \mathbb{Z}\), \(d = \mathrm{pgcd}(a, b)\) avec \(d \mid c\). Si \((x_0, y_0)\) est une solution particulière de \(ax + by = c\), alors l’ensemble des solutions est :

\(\mathcal{S} = \left\{\left(x_0 + \displaystyle\frac{b}{d}\,k,\;\; y_0 – \displaystyle\frac{a}{d}\,k\right) \;\middle|\; k \in \mathbb{Z}\right\}\)

D. Démonstration ⋆

Posons \(a^\prime = \displaystyle\frac{a}{d}\), \(b^\prime = \displaystyle\frac{b}{d}\). On a \(\mathrm{pgcd}(a^\prime, b^\prime) = 1\).

Sens direct. Soit \((x, y) \in \mathbb{Z}^2\) solution. Alors :

\(ax + by = c = ax_0 + by_0 \;\;\Longrightarrow\;\; a(x – x_0) + b(y – y_0) = 0\)

En divisant par \(d\) :

\(a^\prime(x – x_0) = -b^\prime(y – y_0)\)

Donc \(b^\prime \mid a^\prime(x – x_0)\). Comme \(\mathrm{pgcd}(a^\prime, b^\prime) = 1\), le lemme de Gauss donne \(b^\prime \mid (x – x_0)\).

Il existe donc \(k \in \mathbb{Z}\) tel que \(x – x_0 = b^\prime k\). En reportant :

\(a^\prime b^\prime k = -b^\prime(y – y_0) \;\;\Longrightarrow\;\; y – y_0 = -a^\prime k\)

Réciproque. Pour tout \(k \in \mathbb{Z}\), vérifions que \(\left(x_0 + b^\prime k,\; y_0 – a^\prime k\right)\) est bien solution :

\(a(x_0 + b^\prime k) + b(y_0 – a^\prime k) = ax_0 + by_0 + \underbrace{\left(\displaystyle\frac{ab}{d} – \displaystyle\frac{ab}{d}\right)}_{= 0}\,k = c\) ∎

Interprétation géométrique. Les solutions de \(ax + by = c\) dans \(\mathbb{Z}^2\) forment un réseau de points régulièrement espacés sur la droite \(ax + by = c\). Le « pas » entre deux solutions consécutives est le vecteur \(\left(\displaystyle\frac{b}{d},\; -\displaystyle\frac{a}{d}\right)\).

Points entiers sur la droite 3x + 5y = 15 dans le plan cartésien. Axes x de -7 à 12 et y de -4 à 7. Grille légère #e6e8e

III. Méthode de résolution et exemples résolus

La théorie précédente fournit un algorithme complet pour résoudre \(ax + by = c\) dans \(\mathbb{Z}^2\) — ou prouver l’absence de solution.

A. Algorithme en 5 étapes

Méthode de résolution de \(ax + by = c\) dans \(\mathbb{Z}^2\)

  1. Calculer \(d = \mathrm{pgcd}(a, b)\) par l’algorithme d’Euclide.
  2. Tester : \(d \mid c\) ? Si non → aucune solution. Fin.
  3. Remonter l’algorithme d’Euclide pour obtenir les coefficients de Bézout \(u, v\) tels que \(au + bv = d\).
  4. Déduire une solution particulière : \((x_0, y_0) = \left(u \cdot \displaystyle\frac{c}{d},\; v \cdot \displaystyle\frac{c}{d}\right)\).
  5. Écrire l’ensemble des solutions : \(\mathcal{S} = \left\{\left(x_0 + \displaystyle\frac{b}{d}\,k,\; y_0 – \displaystyle\frac{a}{d}\,k\right) \;\middle|\; k \in \mathbb{Z}\right\}\).

Étape optionnelle : Si on cherche les solutions dans \(\mathbb{N}^2\), encadrer \(k\) par les contraintes \(x \geq 0\) et \(y \geq 0\).

Résolution de ax + by = c — Tableau récapitulatif
Étape Action Résultat
1 Algorithme d’Euclide \(d = \mathrm{pgcd}(a, b)\)
2 \(d \mid c\) ? Oui → continuer. Non → \(\mathcal{S} = \emptyset\)
3 Remontée de l’algorithme \(au + bv = d\)
4 Multiplier par \(c/d\) \((x_0, y_0) = (uc/d,\; vc/d)\)
5 Formule générale \(\left(x_0 + \displaystyle\frac{b}{d}\,k,\; y_0 – \displaystyle\frac{a}{d}\,k\right)\), \(k \in \mathbb{Z}\)

Voyons cette méthode en action sur quatre exemples de difficulté croissante.

B. Exemple ★ — Résolution de \(15x + 7y = 1\)

Exemple 1. Résoudre dans \(\mathbb{Z}^2\) : \(15x + 7y = 1\).

Étape 1. Algorithme d’Euclide :

\(15 = 2 \times 7 + 1, \qquad 7 = 7 \times 1 + 0\)

Donc \(d = \mathrm{pgcd}(15, 7) = 1\).

Étape 2. \(1 \mid 1\) ✓ — des solutions existent.

Étape 3. Remontée : \(1 = 15 – 2 \times 7\), d’où \(u = 1,\; v = -2\).

Étape 4. Comme \(c/d = 1\), la solution particulière est \((x_0, y_0) = (1, -2)\).

Vérification : \(15(1) + 7(-2) = 15 – 14 = 1\) ✓

Étape 5. Avec \(b/d = 7\) et \(a/d = 15\) :

\(\mathcal{S} = \left\{(1 + 7k,\; -2 – 15k) \;\middle|\; k \in \mathbb{Z}\right\}\)

C. Exemple ★★ — Résolution de \(12x + 8y = 20\)

Exemple 2. Résoudre dans \(\mathbb{Z}^2\) : \(12x + 8y = 20\).

Étape 1. Algorithme d’Euclide :

\(12 = 1 \times 8 + 4, \qquad 8 = 2 \times 4 + 0\)

Donc \(d = \mathrm{pgcd}(12, 8) = 4\).

Étape 2. \(4 \mid 20\) ✓ — des solutions existent.

Étape 3. Remontée : \(4 = 12 – 1 \times 8\), d’où \(u = 1,\; v = -1\).

Étape 4. \(\displaystyle\frac{c}{d} = \displaystyle\frac{20}{4} = 5\). Solution particulière : \((x_0, y_0) = (5, -5)\).

Vérification : \(12(5) + 8(-5) = 60 – 40 = 20\) ✓

Étape 5. Avec \(\displaystyle\frac{b}{d} = \displaystyle\frac{8}{4} = 2\) et \(\displaystyle\frac{a}{d} = \displaystyle\frac{12}{4} = 3\) :

\(\mathcal{S} = \left\{(5 + 2k,\; -5 – 3k) \;\middle|\; k \in \mathbb{Z}\right\}\)

D. Exemple ★★★ — Solutions dans \(\mathbb{N}^2\) de \(7x + 5y = 123\)

Exemple 3. Déterminer toutes les solutions \((x, y) \in \mathbb{N}^2\) de \(7x + 5y = 123\).

Résolution dans \(\mathbb{Z}^2\) d’abord. On a \(\mathrm{pgcd}(7, 5) = 1 \mid 123\) ✓.

Coefficients de Bézout : \(7 \times 3 + 5 \times (-4) = 21 – 20 = 1\).

Multiplication par 123 : \((x_0, y_0) = (369, -492)\).

Ensemble des solutions dans \(\mathbb{Z}^2\) : \(x = 369 + 5k,\; y = -492 – 7k\).

Contrainte \(x \geq 0\) : \(369 + 5k \geq 0 \;\Longrightarrow\; k \geq -73{,}8 \;\Longrightarrow\; k \geq -73\).

Contrainte \(y \geq 0\) : \(-492 – 7k \geq 0 \;\Longrightarrow\; k \leq -70{,}28\ldots \;\Longrightarrow\; k \leq -71\).

D’où \(k \in \{-73,\; -72,\; -71\}\) et les trois solutions :

Solutions dans ℕ²
\(k\) \(x\) \(y\) Vérification
\(-73\) \(4\) \(19\) \(28 + 95 = 123\) ✓
\(-72\) \(9\) \(12\) \(63 + 60 = 123\) ✓
\(-71\) \(14\) \(5\) \(98 + 25 = 123\) ✓

E. Exemple ★★★★ — Lien avec les congruences

L’un des points les plus puissants du programme est le pont entre équations diophantiennes et congruences : résoudre \(ax \equiv c \;[n]\) revient exactement à résoudre une équation diophantienne.

Exemple 4. Résoudre \(37x \equiv 5 \;[23]\).

Traduction diophantienne. \(37x \equiv 5 \;[23]\) signifie \(\exists\, y \in \mathbb{Z},\; 37x – 23y = 5\).

Algorithme d’Euclide sur \((37, 23)\) :

\(37 = 1 \times 23 + 14\)

\(23 = 1 \times 14 + 9\)

\(14 = 1 \times 9 + 5\)

\(9 = 1 \times 5 + 4\)

\(5 = 1 \times 4 + 1\)

\(\mathrm{pgcd}(37, 23) = 1 \mid 5\) ✓.

Remontée :

\(1 = 5 – 4 = 5 – (9 – 5) = 2 \times 5 – 9\)

\(= 2(14 – 9) – 9 = 2 \times 14 – 3 \times 9\)

\(= 2 \times 14 – 3(23 – 14) = 5 \times 14 – 3 \times 23\)

\(= 5(37 – 23) – 3 \times 23 = 5 \times 37 – 8 \times 23\)

Donc \(37 \times 5 – 23 \times 8 = 1\). Pour \(37x – 23y = 5\), on multiplie par 5 : \((x_0, y_0) = (25, 40)\).

Vérification : \(37 \times 25 – 23 \times 40 = 925 – 920 = 5\) ✓.

Solutions : \(x = 25 – 23k\). Modulo 23 :

\(x \equiv 2 \;[23]\)

Vérification : \(37 \times 2 = 74 = 3 \times 23 + 5\), donc \(37 \times 2 \equiv 5 \;[23]\) ✓.

Logo-excellence-maths
Progresse rapidement en maths sup avec un suivi d'excellence
Un professeur diplômé de Polytechnique t'accompagne pas à pas pour maîtriser l'arithmétique et tous les chapitres de Maths Sup. Résultats visibles dès les premières semaines.
Découvrir l'accompagnement Maths Sup

IV. Extensions : théorème chinois et au-delà

La résolution de \(ax + by = c\) ouvre la porte à des résultats plus avancés. Deux extensions méritent une attention particulière.

A. Théorème chinois des restes

Le théorème chinois des restes (TCR) résout des systèmes de congruences simultanées — et sa démonstration repose directement sur l’existence de solutions d’une équation diophantienne.

Théorème chinois des restes

Soient \(n_1, n_2 \in \mathbb{N}^*\) avec \(\mathrm{pgcd}(n_1, n_2) = 1\), et \(a_1, a_2 \in \mathbb{Z}\). Le système :

\(\begin{cases} x \equiv a_1 \;[n_1] \\ x \equiv a_2 \;[n_2] \end{cases}\)

admet une solution, et l’ensemble des solutions est une unique classe de congruence modulo \(n_1 n_2\).

Esquisse de preuve. La première congruence donne \(x = a_1 + n_1 t\). La seconde impose \(n_1 t \equiv a_2 – a_1 \;[n_2]\), soit \(n_1 t – n_2 s = a_2 – a_1\) — une équation diophantienne en \((t, s)\). Comme \(\mathrm{pgcd}(n_1, n_2) = 1 \mid (a_2 – a_1)\), elle admet toujours une solution. L’unicité modulo \(n_1 n_2\) découle de la structure des solutions. ∎

Généralisation : le TCR s’étend à \(r\) congruences modulo \(n_1, \ldots, n_r\) deux à deux premiers entre eux. La solution est unique modulo \(n_1 \cdots n_r\). La preuve se fait par récurrence en appliquant le cas \(r = 2\).

B. Aperçu des équations diophantiennes non linéaires

Au-delà du cas linéaire, le monde des équations diophantiennes non linéaires est d’une richesse et d’une difficulté considérables. Deux résultats historiques :

  • Triplets pythagoriciens : les solutions de \(x^2 + y^2 = z^2\) dans \(\mathbb{N}^*\) sont entièrement décrites par la paramétrisation \((x, y, z) = (m^2 – n^2,\; 2mn,\; m^2 + n^2)\) avec \(m\) > \(n\) > \(0\), \(\mathrm{pgcd}(m, n) = 1\) et \(m \not\equiv n \;[2]\) (à permutation de \(x\) et \(y\) près).
  • Dernier théorème de Fermat : pour \(n \geq 3\), l’équation \(x^n + y^n = z^n\) n’a aucune solution \((x, y, z) \in \mathbb{Z}^*\). Conjecturé en 1637, démontré par Andrew Wiles en 1995 au moyen de la théorie des courbes elliptiques et des formes modulaires — un tour de force de 129 pages.

Ces résultats ne sont pas au programme de CPGE, mais ils illustrent à quel point le passage de « solutions dans \(\mathbb{R}\) » à « solutions dans \(\mathbb{Z}\) » est un saut conceptuel majeur.

V. Exercices corrigés

Huit exercices classés par difficulté croissante, de l’application directe aux problèmes de concours. Chaque correction est détaillée pas à pas.

Exercice 1 (★ I) — Application directe

Résoudre dans \(\mathbb{Z}^2\) l’équation \(7x + 4y = 1\).

Voir la correction

Algorithme d’Euclide : \(7 = 1 \times 4 + 3\), \(4 = 1 \times 3 + 1\), \(3 = 3 \times 1\). Donc \(\mathrm{pgcd}(7, 4) = 1 \mid 1\) ✓.

Remontée : \(1 = 4 – 1 \times 3 = 4 – (7 – 4) = 2 \times 4 – 7\).

D’où \(7 \times (-1) + 4 \times 2 = 1\). Solution particulière : \((x_0, y_0) = (-1, 2)\).

Solutions :

\(\mathcal{S} = \{(-1 + 4k,\; 2 – 7k) \mid k \in \mathbb{Z}\}\)

Exercice 2 (★★ I) — PGCD non trivial

Résoudre dans \(\mathbb{Z}^2\) l’équation \(18x + 12y = 24\).

Voir la correction

Algorithme d’Euclide : \(18 = 1 \times 12 + 6\), \(12 = 2 \times 6\). Donc \(d = \mathrm{pgcd}(18, 12) = 6\). Or \(6 \mid 24\) ✓.

Remontée : \(6 = 18 – 1 \times 12\). Soit \(18(1) + 12(-1) = 6\).

Multiplication par \(\displaystyle\frac{24}{6} = 4\) : \((x_0, y_0) = (4, -4)\). Vérification : \(72 – 48 = 24\) ✓.

Avec \(\displaystyle\frac{b}{d} = 2\) et \(\displaystyle\frac{a}{d} = 3\) :

\(\mathcal{S} = \{(4 + 2k,\; -4 – 3k) \mid k \in \mathbb{Z}\}\)

Exercice 3 (★★) — Algorithme d’Euclide à plusieurs étapes

Résoudre dans \(\mathbb{Z}^2\) l’équation \(119x + 91y = 7\).

Voir la correction

Algorithme d’Euclide :

\(119 = 1 \times 91 + 28, \qquad 91 = 3 \times 28 + 7, \qquad 28 = 4 \times 7\)

Donc \(d = \mathrm{pgcd}(119, 91) = 7 \mid 7\) ✓.

Remontée :

\(7 = 91 – 3 \times 28 = 91 – 3(119 – 91) = 4 \times 91 – 3 \times 119\)

D’où \(119 \times (-3) + 91 \times 4 = 7\). Comme \(\displaystyle\frac{c}{d} = 1\), on a directement \((x_0, y_0) = (-3, 4)\).

Vérification : \(-357 + 364 = 7\) ✓.

Avec \(\displaystyle\frac{91}{7} = 13\) et \(\displaystyle\frac{119}{7} = 17\) :

\(\mathcal{S} = \{(-3 + 13k,\; 4 – 17k) \mid k \in \mathbb{Z}\}\)

Exercice 4 (★★★) — Solutions dans \(\mathbb{N}^2\)

Déterminer toutes les solutions \((x, y) \in \mathbb{N}^2\) de \(11x + 7y = 200\).

Voir la correction

\(\mathrm{pgcd}(11, 7) = 1 \mid 200\) ✓. Bézout : \(11 \times 2 + 7 \times (-3) = 1\) (car \(22 – 21 = 1\)).

Multiplication par 200 : \((x_0, y_0) = (400, -600)\). Solutions dans \(\mathbb{Z}^2\) : \(x = 400 + 7k,\; y = -600 – 11k\).

Contraintes :

  • \(x \geq 0 \;\Longrightarrow\; k \geq -57{,}14\ldots \;\Longrightarrow\; k \geq -57\)
  • \(y \geq 0 \;\Longrightarrow\; k \leq -54{,}54\ldots \;\Longrightarrow\; k \leq -55\)

D’où \(k \in \{-57, -56, -55\}\) :

  • \(k = -57\) : \((1, 27)\). Vérification : \(11 + 189 = 200\) ✓
  • \(k = -56\) : \((8, 16)\). Vérification : \(88 + 112 = 200\) ✓
  • \(k = -55\) : \((15, 5)\). Vérification : \(165 + 35 = 200\) ✓

Exercice 5 (★★★) — Congruence et équation diophantienne

Résoudre dans \(\mathbb{Z}\) l’équation \(6x \equiv 15 \;[21]\).

Voir la correction

Traduction : \(6x \equiv 15 \;[21] \;\Longleftrightarrow\; \exists\, y \in \mathbb{Z},\; 6x – 21y = 15\).

On simplifie par \(\mathrm{pgcd}(6, 21, 15) = 3\) : \(2x – 7y = 5\).

\(\mathrm{pgcd}(2, 7) = 1 \mid 5\) ✓. Bézout : \(2 \times 4 – 7 \times 1 = 1\).

Multiplication par 5 : \((x_0, y_0) = (20, 5)\). Vérification : \(40 – 35 = 5\) ✓.

Solutions dans \(\mathbb{Z}^2\) : \(x = 20 – 7k,\; y = 5 – 2k\).

Modulo 7 : \(x \equiv 20 \equiv 6 \;[7]\).

Les solutions modulo 21 sont \(x \in \{6, 13, 20\}\) (trois classes, car \(\mathrm{pgcd}(6, 21) = 3\)).

Vérification : \(6 \times 6 = 36 \equiv 15 \;[21]\) ✓, \(6 \times 13 = 78 \equiv 15 \;[21]\) ✓, \(6 \times 20 = 120 \equiv 15 \;[21]\) ✓.

Exercice 6 (★★★★) — Théorème chinois des restes

Trouver le plus petit entier naturel \(x\) vérifiant simultanément \(x \equiv 2 \;[5]\), \(x \equiv 3 \;[7]\) et \(x \equiv 4 \;[11]\).

Voir la correction

Étape 1 : combiner les deux premières congruences.

\(x = 2 + 5t\). Condition : \(2 + 5t \equiv 3 \;[7]\), soit \(5t \equiv 1 \;[7]\).

Inverse de 5 modulo 7 : \(5 \times 3 = 15 \equiv 1 \;[7]\), donc \(t \equiv 3 \;[7]\).

\(t = 3 + 7s\) \(\Longrightarrow\) \(x = 2 + 5(3 + 7s) = 17 + 35s\). D’où \(x \equiv 17 \;[35]\).

Étape 2 : ajouter la troisième congruence.

\(17 + 35s \equiv 4 \;[11]\). Or \(35 \equiv 2 \;[11]\) et \(17 \equiv 6 \;[11]\), donc \(2s \equiv -2 \equiv 9 \;[11]\).

Inverse de 2 modulo 11 : \(2 \times 6 = 12 \equiv 1 \;[11]\), donc \(s \equiv 6 \times 9 \equiv 54 \equiv 10 \;[11]\).

\(s = 10 + 11u\) \(\Longrightarrow\) \(x = 17 + 35(10 + 11u) = 367 + 385u\).

Conclusion : \(x \equiv 367 \;[385]\), et le plus petit entier naturel est \(x = 367\).

Vérification : \(367 = 73 \times 5 + 2\) ✓, \(367 = 52 \times 7 + 3\) ✓, \(367 = 33 \times 11 + 4\) ✓.

Exercice 7 (★★★★) — Entiers non représentables (cas concret)

On pose \(a = 3\) et \(b = 5\). Déterminer l’ensemble de tous les entiers naturels \(n\) qui ne peuvent pas s’écrire sous la forme \(3x + 5y\) avec \((x, y) \in \mathbb{N}^2\). Quel est le plus grand d’entre eux ?

Voir la correction

On teste systématiquement les petites valeurs de \(n\) :

  • \(n = 0\) : \((0, 0)\) ✓
  • \(n = 1\) : aucune solution (le plus petit \(3x + 5y\) > \(0\) est \(\min(3, 5) = 3\)) ✗
  • \(n = 2\) : aucune solution ✗
  • \(n = 3\) : \((1, 0)\) ✓
  • \(n = 4\) : aucune solution (\(3x + 5y = 4\) impossible pour \(x, y \in \mathbb{N}\)) ✗
  • \(n = 5\) : \((0, 1)\) ✓
  • \(n = 6\) : \((2, 0)\) ✓
  • \(n = 7\) : aucune solution ✗
  • \(n = 8\) : \((1, 1)\) ✓

Pour \(n \geq 8\), on raisonne par classes modulo 3 :

  • \(n \equiv 0 \;[3]\) : \(n = 3 \cdot \displaystyle\frac{n}{3}\) ✓
  • \(n \equiv 2 \;[3]\) et \(n \geq 5\) : \(n – 5 \geq 0\) et \(n – 5 \equiv 0 \;[3]\), donc \(n = 3 \cdot \displaystyle\frac{n-5}{3} + 5\) ✓
  • \(n \equiv 1 \;[3]\) et \(n \geq 10\) : \(n – 10 \geq 0\) et \(n – 10 \equiv 0 \;[3]\), donc \(n = 3 \cdot \displaystyle\frac{n-10}{3} + 2 \times 5\) ✓

L’ensemble des non représentables est \(\{1, 2, 4, 7\}\) : il y en a 4, et le plus grand est \(7 = 3 \times 5 – 3 – 5 = ab – a – b\).

On vérifie aussi : \(4 = \displaystyle\frac{(3-1)(5-1)}{2} = \displaystyle\frac{2 \times 4}{2}\). Ce nombre n’est pas une coïncidence (cf. exercice 8).

Exercice 8 (★★★★★) — Nombre de Frobenius [Type concours X/ENS]

Soient \(a, b \in \mathbb{N}^*\) avec \(\mathrm{pgcd}(a, b) = 1\). On dit que \(n \in \mathbb{N}\) est représentable s’il existe \((x, y) \in \mathbb{N}^2\) tel que \(ax + by = n\).

  1. Montrer que \(N = ab – a – b\) n’est pas représentable.
  2. Montrer que tout entier \(n\) > \(ab – a – b\) est représentable.
Voir la correction

1) \(N = ab – a – b\) n’est pas représentable.

Remarquons que \(a(b-1) + b(-1) = ab – a – b\), donc \((x_0, y_0) = (b-1, -1)\) est une solution particulière dans \(\mathbb{Z}^2\).

L’ensemble des solutions est \(x = (b-1) + bk,\; y = -1 – ak\) pour \(k \in \mathbb{Z}\).

Contrainte \(x \geq 0\) : \((b-1) + bk \geq 0 \;\Longrightarrow\; k \geq -\displaystyle\frac{b-1}{b}\) > \(-1 \;\Longrightarrow\; k \geq 0\).

Contrainte \(y \geq 0\) : \(-1 – ak \geq 0 \;\Longrightarrow\; k \leq -\displaystyle\frac{1}{a}\) < \(0 \;\Longrightarrow\; k \leq -1\).

Les deux contraintes \(k \geq 0\) et \(k \leq -1\) sont incompatibles. Donc \(N\) n’est pas représentable. ∎

2) Tout \(n\) > \(ab – a – b\) est représentable.

Soit \(n \geq ab – a – b + 1\). Comme \(\mathrm{pgcd}(a, b) = 1\), il existe un unique \(x^* \in \{0, 1, \ldots, b-1\}\) tel que \(ax^* \equiv n \;[b]\).

Posons \(y^* = \displaystyle\frac{n – ax^*}{b} \in \mathbb{Z}\). Alors \(x^* \geq 0\) par construction, et :

\(y^* = \displaystyle\frac{n – ax^*}{b} \geq \displaystyle\frac{n – a(b-1)}{b} = \displaystyle\frac{n – ab + a}{b}\)

Pour \(n \geq ab – a – b + 1\) :

\(y^* \geq \displaystyle\frac{ab – a – b + 1 – ab + a}{b} = \displaystyle\frac{1 – b}{b}\) > \(-1\)

Comme \(y^* \in \mathbb{Z}\) et \(y^*\) > \(-1\), on a \(y^* \geq 0\). Le couple \((x^*, y^*) \in \mathbb{N}^2\) convient. ∎

Remarque. Le nombre \(g(a, b) = ab – a – b\) est appelé nombre de Frobenius de \((a, b)\). On peut montrer (argument de symétrie par l’involution \(n \mapsto ab – a – b – n\)) que le nombre d’entiers non représentables est exactement \(\displaystyle\frac{(a-1)(b-1)}{2}\) — un résultat dû à Sylvester (1884).

🎁 EN BONUS

L’essentiel du cours sur les équations diophantiennes en 1 fiche

Théorèmes, méthode en 5 étapes, formules clés et pièges à éviter — tout sur une page, prête à imprimer pour tes révisions.

📄 Télécharger la fiche de synthèse

Le mémo indispensable pour ne plus jamais confondre b et b/d dans la formule des solutions.

VI. Erreurs fréquentes et rédaction concours

A. Copie fautive commentée

Voici une erreur réellement observée en DS de Maths Sup, sur l’exercice « Résoudre dans \(\mathbb{Z}^2\) : \(12x + 8y = 20\) ».

❌ Copie de l’élève

« pgcd(12, 8) = 4 et 4 | 20, donc il y a des solutions.

Bézout : 12(1) + 8(−1) = 4. Pour 12x + 8y = 20, on multiplie par 5 : x₀ = 5, y₀ = −5.

L’ensemble des solutions est S = {(5 + 8k, −5 − 12k) | k ∈ ℤ}. »

Diagnostic : L’erreur porte sur l’étape 5 — la formule de l’ensemble des solutions. L’élève a utilisé \(b = 8\) et \(a = 12\) au lieu de \(\displaystyle\frac{b}{d} = 2\) et \(\displaystyle\frac{a}{d} = 3\). Son ensemble de solutions est un sous-ensemble strict du vrai ensemble : il manque des solutions.

Conséquence concrète : la vraie solution \((7, -8)\) (obtenue avec \(k = 1\) dans la bonne formule) n’apparaît pas dans l’ensemble proposé. Vérification : \(12 \times 7 + 8 \times (-8) = 84 – 64 = 20\) ✓ — c’est bien une solution, pourtant absente de la copie.

✅ Correction :

\(\mathcal{S} = \left\{\left(5 + \displaystyle\frac{8}{4}\,k,\; -5 – \displaystyle\frac{12}{4}\,k\right) \;\middle|\; k \in \mathbb{Z}\right\} = \{(5 + 2k,\; -5 – 3k) \mid k \in \mathbb{Z}\}\)

Autre erreur classique : oublier le test de divisibilité

Certains élèves lancent l’algorithme d’Euclide et la remontée de Bézout avant de vérifier si \(d \mid c\). Pour une équation sans solution (comme \(6x + 9y = 4\) avec \(d = 3\) et \(3\) ne divise pas \(4\)), ils s’embrouillent dans des calculs inutiles et concluent tardivement à l’absence de solution — voire concluent à tort qu’il y en a.

Règle d’or : toujours tester \(d \mid c\) immédiatement après le calcul du pgcd.

B. Ce que le correcteur attend

Rédaction type pour un exercice d’équation diophantienne en concours :

  1. Calcul du pgcd par l’algorithme d’Euclide, écrit proprement sous forme de divisions euclidiennes successives.
  2. Conclusion explicite sur l’existence : « Comme \(d \mid c\), l’équation admet des solutions dans \(\mathbb{Z}^2\) » ou « Comme \(d\) ne divise pas \(c\), l’équation n’a aucune solution. » — phrase obligatoire.
  3. Remontée de Bézout avec vérification de la solution particulière.
  4. Formule générale avec \(\displaystyle\frac{b}{d}\) et \(\displaystyle\frac{a}{d}\) — pas \(b\) et \(a\).
  5. Vérification sur au moins un couple, en substituant dans l’équation d’origine.
  6. Si solutions dans \(\mathbb{N}^2\) : encadrement explicite de \(k\) avec justification de chaque inégalité, puis liste exhaustive des solutions.

Le correcteur sanctionne systématiquement : (a) l’absence du test \(d \mid c\), (b) la confusion \(b\) / \(b/d\) dans la formule, (c) l’absence de vérification.

VII. Questions fréquentes

Qu'est-ce qu'une équation diophantienne ?

Une équation diophantienne est une équation polynomiale à coefficients entiers dont on cherche les solutions dans \(\mathbb{Z}\) (ou \(\mathbb{N}\)), et non dans \(\mathbb{R}\). En CPGE, on étudie principalement le cas linéaire \(ax + by = c\), résolu grâce au PGCD et au théorème de Bézout.

Comment résoudre une équation diophantienne ax + by = c ?

La méthode complète comporte 5 étapes : (1) calculer \(d = \mathrm{pgcd}(a, b)\) par l’algorithme d’Euclide ; (2) vérifier que \(d \mid c\) (sinon, aucune solution) ; (3) remonter l’algorithme pour obtenir les coefficients de Bézout ; (4) en déduire une solution particulière ; (5) écrire l’ensemble des solutions à l’aide de la formule paramétrée.

Quelle est la différence entre une équation diophantienne et un système d'équations ?

Un système d’équations à deux inconnues dans \(\mathbb{R}\) cherche un point d’intersection de deux droites — il a en général une unique solution réelle. Une équation diophantienne \(ax + by = c\) est une seule équation, mais la contrainte \((x, y) \in \mathbb{Z}^2\) remplace la seconde équation : les solutions forment un ensemble discret (fini ou infini dénombrable), jamais un continuum.

Le théorème de Pythagore est-il une équation diophantienne ?

L’équation \(x^2 + y^2 = z^2\) est bien une équation diophantienne (quadratique), et ses solutions entières positives sont les triplets pythagoriciens comme \((3, 4, 5)\) ou \((5, 12, 13)\). Mais elle ne relève pas des mêmes méthodes que l’équation linéaire \(ax + by = c\) : sa résolution utilise une paramétrisation spécifique, pas le théorème de Bézout.

Pourquoi les équations diophantiennes sont-elles au programme de CPGE ?

L’équation \(ax + by = c\) dans \(\mathbb{Z}^2\) concentre tous les outils du chapitre d’arithmétique : divisibilité, PGCD, algorithme d’Euclide, théorème de Bézout, lemme de Gauss, congruences et théorème chinois des restes. C’est un sujet récurrent en colles, en DS et dans les épreuves écrites de concours (X, Mines-Ponts, Centrale), souvent combiné avec des problèmes de dénombrement ou de théorie des nombres.

VIII. Pour aller plus loin

Tu maîtrises maintenant la résolution complète des équations diophantiennes linéaires. Pour consolider et élargir tes compétences en arithmétique :

Logo-excellence-maths
Prêt à exceller en prépa scientifique ?
Avec un professeur diplômé de Polytechnique à tes côtés, tu structures ta pensée, tu gagnes en rigueur et tu vises le top. Premier cours satisfait ou remboursé.
Démarrer mon accompagnement