Exercices - Equations diophantiennes : corrigé

Exercice 1 - Une équation de Bezout - L1/Math Sup - ?

On commence par rechercher le pgcd de 323 et 391 en appliquant par exemple l’algorithme
d’Euclide. On a :

391 = 323 × 1 + 68
323 = 68 × 4 + 51
68 = 51 × 1 + 17
51 = 17 × 3

Ainsi, le pgcd de 391 et 323 est 17. On vérifie que 17 divise 612, car 612 = 17 × 36. D’autre
part, 391 = 17 × 23 et 323 = 17 × 19. L’équation est donc équivalente à

19x − 23y = 36.

D’après le théorème de Bezout, puisque 19 et 23 sont premiers entre eux, on sait qu’il existe
(x0 , y0 ) solution de 19x−23y = 1. Multipliant tout par 36, (36x0 , 36y0 ) est solution de l’équation.
Soit (x, y) une solution de l’équation. Alors on a

19(x − 36x0 ) − 23(y − 36y0 ) = 0.

Ainsi, 19 divise 23(y − 36y0 ). Mais puisque 19 et 23 sont premiers entre eux, 19 divise (y − 36y0 )
et donc il existe un entier k tel que y = 36y0 +19k. Reportant cela dans l’équation, on trouve que
x = 36y0 + 23k. Réciproquement, il est facile de vérifier que tout couple (36y0 + 23k, 36y0 + 19k)
est solution. Il suffit donc de déterminer un couple (x0 , y0 ).
On applique une nouvelle fois l’algorithme d’Euclide :

23 = 19 + 4
19 = 4 × 4 + 3
4 = 3+1

soit, en remontant les calculs :

1 = 4 − (19 − 4 × 4) = 5 × 4 − 19 = 5 × (23 − 19) − 19 = 5 × 23 − 6 × 19.

On peut donc prendre x0 = −6 et y0 = −5. L’ensemble des solutions de l’équation est donc

{(−216 + 23k, −180 + 19k), k ∈ Z}.

Exercice 2 - Bezout à coefficients positifs - L1/Math Sup - ??

L’équation au + bv = x a toujours une solution (u0 , v0 ) dans Z2 d’après le théorème de
Bezout. De plus, l’ensemble des solutions est constitué par les couples (uk , vk ) avec uk = u + kb,
vk = v − ka. Puisque (uk )k∈Z est croissante, tend vers −∞ en −∞ et vers +∞ en +∞, il existe
un entier k tel que uk−1 ≤ 0 ≤ uk . Montrons que vk ≥ 0. Pour cela, on écrit

x = auk + bvk = a(uk−1 + b) + bvk

soit
bvk = x − ab − auk−1 .

http://www.bibmath.net 1
 Exercices - Equations diophantiennes : corrigé

Puisque x − ab ≥ 0 et auk−1 ≤ 0, on en déduit bvk ≥ 0, ou encore vk ≥ 0.

Exercice 3 - Le magicien des mathématiques - Math Sup/L1 - ??
En notant j le jour de naissances et m le mois de naissances, on doit résoudre

12m + 31j = 811.

C’est une équation de Bézout, qu’on peut résoudre "naïvement", mais c’est bien sûr impossible
de tête. L’idée est que l’on sait que m est forcément compris entre 1 et 12. On regarde la
congruence modulo 31, et on obtient 12m ≡ 811 [31] ≡ 5 [31]. Mais, pour m allant de 1 à 12,
les entiers 12m ont des congruences modulo 31 différentes les unes des autres. Ainsi, on trouve
dans l’autre 12, 24, 5, 17, 29, 10, 22, 3, 15, 27, 8, 20. Ceci nous donne immédiatement m = 3, puis,
en retournant à l’équation 12m + 31j = 811, j = 25.
Exercice 4 - Congruences simultanée - Problème du cuisiner chinois - L1/Math Sup
- ??

1. Puisque n ∧ m = 1, le théorème de Bezout nous donne l’existence de u, v ∈ Z tel que

un + vm = 1. L’équation nx ≡ a [m] implique unx ≡ ua [m]. Or, un ≡ 1[m] et donc
l’équation devient x ≡ ua[m]. Réciproquement, si x ≡ ua [m], alors nx ≡ nua ≡ a[m].
Ainsi, l’ensemble des solutions de l’équation est {ua + mk; k ∈ Z}.
2. On a l’ équivalence suivante :
( (
x ≡ a [n] ∃k ∈ Z, x = a + nk
⇐⇒
x ≡ b [m] nk ≡ b − a [m].

On applique alors le résultat de la question précédente pour obtenir les valeurs possibles
de k. Soit (u, v) ∈ Z2 tels que un + vm = 1.
( (
x ≡ a [n] ∃k ∈ Z, x = a + nk
⇐⇒
x ≡ b [m] k ≡ u(b − a) [m]
(
∃k ∈ Z, x = a + nk
⇐⇒
∃l ∈ Z, k = u(b − a) + ml.

On remplace alors k par sa valeur dans la première équation, et on trouve que x est
solution si et seulement si il existe l ∈ Z tel que x = a + nu(b − a) + nml. On obtient bien
des solutions qui sont uniques modulo nm.
3. On commence par mettre en équation le problème. Soit x les temps, en secondes depuis
minuit, où les deux phares sont allumés au même moment. Les données du problème nous
disent que x est solution du système :
(
x ≡ 2 [15]
x ≡ 8 [28].

On cherche le plus petit entier naturel x solution de ce système. Comme 15 ∧ 28 = 1, on

peut appliquer les résultats de la question précédente. Il suffit de chercher (u, v) tels que

http://www.bibmath.net 2
 Exercices - Equations diophantiennes : corrigé

15u + 28v = 1. On applique l’algorithme d’Euclide :

28 = 15 × 1 + 13
15 = 13 × 1 + 2
13 = 6 × 2 + 1

soit, en remontant les calculs

1 = −6 × 2 + 1 × 13
= −6 × (15 − 13) + 13 = 7 × 13 − 6 × 15
= 7 × (28 − 15) − 6 × 15
= 7 × 28 − 13 × 15.

x est donc le plus petit entier naturel de

{2 + 15 × (−13) × (8 − 2) + 28 × 15 × k; k ∈ Z} = {−1168 + 420k; k ∈ Z}.

Le plus petit entier naturel de cet ensemble est obtenu pour k = 3, et on trouve x = 92 :
les deux phares seront allumés au même moment pour la première fois 1 minute et 32
secondes après minuit.
4. Là encore, il faut traduire ceci en termes de congruences. On a :

 x
 ≡ 3 [17]
x ≡ 4 [11]
 x ≡ 5 [6]


Ce problème se traite exactement de la même façon. On peut aussi résoudre d’abord les
deux premières équations ensembles, puis introduire dans la troisième. Ici, tout est facilité
si on remarque que 37 est tel que 37 ≡ 3 [17] et 37 ≡ 4 [11]. Puisque 17 ∧ 11 = 1, on sait
d’après la deuxième question que
(
x ≡ 3 [17]
⇐⇒ x ≡ 37[187].
x ≡ 4 [11]

On doit donc résoudre le système

(
x ≡ 37 [187]
x ≡ 5 [6].

Or, 1 = 1 × 187 − 6 × 37. L’ensemble des solutions de ce système est donc :

{37 + 187 × 1 × (5 − 37) + 1122k; k ∈ Z} = {−5947 + 1122k; k ∈ Z}.

Le plus petit entier positif est obtenu pour k = 6 et donne 785. Le cuisinier est sûr
d’obtenir au moins 785 pièces d’or.

Exercice 5 - Equations du second degré - L1/Math Sup - ??

http://www.bibmath.net 3
 Exercices - Equations diophantiennes : corrigé

1. On remarque que xy = 2x + 3y ⇐⇒ (x − 3)(y − 2) = 6. Ainsi, x − 3|6, ce qui im-

pose x − 3 ∈ {−6, −3, −2, −1, 0, 1, 2, 3, 6} soit encore x ∈ {−3, 0, 1, 2, 3, 4, 5, 6, 9}. Pour
x = 0, on obtient y − 2 = −2, ie y = 0. Pour x = 3, l’équation devient 0 = 6 et n’a
pas de solutions. Pour x = 6, on trouve y − 2 = 2 soit y = 4. Pour x = 9, on ob-
tient y = 3, pour x = −3, y = 1 et ainsi de suite. L’ensemble des solutions est donc
{(−3, 1); (0, 0); (1, −1); (2, −4); (4, 8); (5, 5); (6, 4); (9, 3)}.
2. On factorise de la même façon en mettant sous forme canonique :
2 2
1 3
 
x2 − y 2 − x + 3y = 30 ⇐⇒ x− − y− = 28 ⇐⇒ (x + y − 2)(x − y + 1) = 28.
2 2
On a donc x+y−2|28 et x+y−2 6= 0 soit x+y−2 ∈ {−28, −14, −7, −4, −2, −1, 1, 2, 4, 7, 14, 28}.
Si x+y −2 = −28, alors x−y +1 = −1, et donc le couple (x, y) correspondant est solution
du système (
x + y = −26
x − y = −2.
On résoud ce système et on trouve x = −14, y = −12. On fait de même pour les autres
cas, et on trouve, sauf erreur, que l’ensemble des solutions est

{(−14, −12); (−5, 0); (−5, 3); (−14, −15); (15, −12); (6, 0); (6, 3); (15, 15)}.

3. On écrit l’équations modulo 5, et on trouve que x2 ≡ 3 ( mod 5). Or, si x ≡ ±1 ( mod 5),
alors x2 ≡ 1 ( mod 5) et si x ≡ ±2 ( mod 5), alors x2 ≡ 4 ( mod 5) et donc l’équation
x2 = 3 ( mod 5) n’a pas de solutions. Ainsi, l’équation de départ n’a pas de solutions
dans Z2 .

Exercice 6 - Pas de solutions rationnelles - L1/Math Sup - ??

Admettons qu’il existe une solution rationnelle x = p/q, avec p ∧ q = 1 et q > 0. Alors,
remplaçant x par p/q dans l’équation et multipliant tout par q 3 , on obtient :

p3 + p2 q + pq 2 + q 3 = 0.

Puisque q|p2 q + pq 2 + q 3 , on obtient q|p3 et donc q = 1 puisque p et q sont premiers entre eux.
En effectuant le même raisonnement avec p, on obtient p = ±1. Or 1 et −1 ne sont pas solutions
de l’équation. Il y a donc contradiction.
Exercice 7 - Fermat modifié - L1/Math Sup - ??

1. On distingue plusieurs cas. Si a et b sont tous deux impairs, a = 2k + 1 et b = 2l + 1,

alors a2 + b2 = 4(k 2 + l2 + k + l) + 2 n’est pas un multiple de 4. Si a est pair et b est
impair, a = 2k et b = 2l + 1, alors a2 + b2 = 4(k 2 + l2 + l) + 1 n’est pas un multiple de
4. Le raisonnement est identique si a est impair et b est pair. Dans tous les cas, pour que
a2 + b2 soit un multiple de 4, il est nécessaire que a et b soient pairs.
2. Imaginons qu’il existe au moins une solution à l’équation, et choisissons une solution
22n = a2 + b2 avec n le plus petit possible. Alors n ≥ 1, car l’équation 20 = 1 = a2 + b2
n’admet pas de solutions avec a ≥ 1 et b ≥ 1. Donc, 22n est un multiple de 4. D’après la
question précédente, a = 2k et b = 2l sont des nombres pairs. Ainsi, on a encore

22n = 4k 2 + 4l2 ⇐⇒ 22(n−1) = k 2 + l2 .

http://www.bibmath.net 4
 Exercices - Equations diophantiennes : corrigé

Ainsi, on a trouvé une solution à l’équation avec n − 1 < n, ce qui contredit la minimalité
de n. Donc l’équation n’admet aucune solution.
3. Démontrons par récurrence sur n que l’équation (portant sur a, b ∈ N∗ ) 22n+1 = a2 + b2
admet pour unique solution a = b = 2n . Pour n = 0, on doit résoudre 2 = a2 + b2 avec
a, b ∈ N∗ , ce qui entraîne bien a = b = 1. Soit n ∈ N et supposons que la propriété est
vraie au rang n. Prouvons-la au rang n + 1. Alors, 22n+3 est un multiple de 4. D’après la
première question, si a2 + b2 = 22(n+1)+1 , alors a = 2k, b = 2l et donc

22n+1 = k 2 + l2 .

Par hypothèse de récurrence, k = l = 2n , et donc a = b = 2n+1 . La propriété est donc

vraie au rang n + 1. Par le principe de récurrence, elle est vraie pour tout n ≥ 0.

http://www.bibmath.net 5