ÉQUATIONS DE DIOPHANTE
Il s'agit des équations de la forme : ax + by = c avec (a, b, c) Î * ´ * ´
a) Déterminer une condition nécessaire et suffisante pour que l'équation admette au moins une solution.
b) Déterminer, dans ce cas, l'ensemble de toutes les solutions.
c) Application : en multipliant mon jour de naissance par 12 et mon mois de naissance par 31, j'obtiens 442.
Quelle est ma date de naissance ? (On ne demande pas l'année, ouf !)
Solution :
a) Posons d = pgcd(a, b).
Soient a' et b' tels que : a = da' et b = db'
D'après l'homogénéité du pgcd, on a alors : a' Ù b' = 1
L'équation s'écrit : d(a'x + b'y) = c
Distinguons deux cas :
· Si d ne divise pas c, alors l'équation n'a pas de solutions.
· Si d divise c, alors on pose c = dc'. Notre équation s'écrit alors :
a'x + b'y = c'
Par ailleurs, comme a' Ù b' = 1, le théorème de Bézout assure l'existence d'un couple (u, v) tel que :
a'u + b'v = 1
En multipliant par c', on a alors : a'c'u + b'c'v = c'
Le couple (c'u, c'v) est donc une solution particulière de l'équation Diophantienne ax + by = c.
Une condition nécessaire et suffisante d'existence de solution est : le pgcd de a et b divise c.
b) On suppose désormais que le pgcd de a et b divise c.
Nous connaissons maintenant une solution particulière (c'u, c'v).
On peut en déduire l'ensemble des solutions. Soit (x, y) une solution quelconque de l'équation ax + by = c.
ì a¢x + b¢y = c ¢
On a alors : í
îa¢c¢u + b¢c¢v = c¢
Par différence, il vient : a'(x - c'u) + b'(y - c'v) = 0
En conséquence : a' | b'(y - c'v)
Et comme a'Ù b' = 1, on a, d'après le théorème de Gauss :
a' | (y - c'v)
Donc : $k Î , y = ka' + c'v
En remplaçant : a'(x - c'u) + b'ka' = 0
Et comme a' ¹ 0 : x = -b'k + c'u
Réciproquement, on vérifie que, pour tout k Î , le couple (-b'k + c'u, ka' + c'v) est bien solution de
l'équation Diophantienne.
Bilan : les couples (x, y) solutions de l'équation ax + by = c (lorsque pgcd(a, b) divise c) sont de la forme :
(x, y) = (-b'k + c'u, ka' + c'v), k Î
c) Notons J et M mon jour et mon mois de naissance respectivement.
On a donc : 12J + 31M = 442
Equations de Diophante. Page 1 G. COSTANTINI http://bacamaths.net/
Comme 12 Ù 31 = 1, l'équation admet des solutions. (Donc je suis bien né !)
On recherche une solution particulière en appliquant l'algorithme d'Euclide-Bézout :
r0 q1 r1 r2
31 = 2 ´12 + 7
r1 q2 r2 r3
12 = 1 ´ 7 + 5
r2 q3 r3 r4
7 = 1 ´5+ 2
r3 q4 r4 r5
5 = 2´2+1
r4 q5 r5 r6
2 = 2 ´1+ 0
Puis, on exprime le pgcd (à savoir 1) en fonction des restes précédents :
1=5-2´2
1 = 5 - 2 ´ (7 - 5) = -2 ´ 7 + 3 ´ 5
1 = - 2 ´ 7 + 3 ´ (12 - 7) = 3 ´ 12 - 5 ´ 7
1 = 3 ´ 12 - 5 ´ (31 - 2 ´ 12) = -5 ´ 31 + 13 ´ 12
Finalement, un couple (u, v) possible est (-5, 13).
On a donc : -5 ´ 31 + 13 ´ 12 = 1
En multipliant par 442 : -2210 ´ 31 + 5746 ´ 12 = 442
Donc le couple (J0, M0) = (5742, -2210) est une solution particulière de l'équation 12J + 31M = 442.
On recherche maintenant l'ensemble de toutes les solutions. Soit (J, M) une solution quelconque.
ì 12 J + 31M = 442
í
î5746 ´ 12 - 2210 ´ 31 = 442
Par différence, il vient : 12(J - 5746) + 31(M + 2210) = 0
En conséquence : 31 | 12(J - 5746)
Et comme 12 Ù 31 = 1, on a, d'après le théorème de Gauss :
31 | J -5746
Donc : $k Î , J = 31k + 5746
Or, évidemment J Î 1, 31 : 1 31k + 5746 31
-5745 31k -5715
k = -185
J = 11
On en déduit : M = 10
Je suis donc né un 11 octobre.
Equations de Diophante. Page 2 G. COSTANTINI http://bacamaths.net/
