Arithmetique

Exemple de résolution d'équations diophantiennes

Exemple 1 : Résoudre l'équation 65x + 104y = 26 où (x ; y) ∈ ℤ².

Avant tout, on vérifie si l'équation peut admettre des solutions !
On a : 65 = 5×13 et 104 = 4×26 = 4×2×13 donc PGCD(65 ; 104) = 13 et 5 et 8 sont premiers entre eux.
Or 26 = 2×13 est bien un multiple du PGCD, donc l'équation admet des solutions.

En divisant par 13, l'équation s'écrit : 5x + 8y = 2

Méthode 1 (classique):

Ici pas besoin d'utiliser les grands moyens pour trouver une solution particulière...
On remarque que 5×2 + 8×(-1) = 2. Une solution particulière est (2 ; -1).
Ainsi d'une part 5x + 8y = 2 et d'autre part 5×2 + 8×(-1) = 2, donc 5x + 8y = 5×2 + 8×(-1).
Soit encore 5(x - 2) = 8(-y - 1). or 5 et 8 sont premiers entre eux et d'après le théorème de Gauss 5 divise -y - 1.
Il existe donc k ∈ ℤ tel que -y - 1 = 5k, c'est-à-dire y = -5k -1.
En reportant dans l'équation précédente, on obtient : 5(x - 2) = 8(5k + 1 - 1).
Soit 5x -10 = 8×5k. En divisant par 5 on a, x -2 = 8k, d'où x = 8k + 2.
On vérifie avec l'équation initiale :
5(8k + 2) + 8(-5k -1) = 40k + 10 -40 k - 8 = 2. Ok !
Les solutions de l'équation sont les couples (8k + 2 ; -5k -1) avec k ∈ ℤ.

Méthode 2 (fonction):

Avec la calculatrice on dresse un tableau de valeurs de la fonction f(x) =(-5x +2)/8 de telle sorte que 2 couples solutions apparaisent...
Ici pas besson de chercher longtemps. Pour x ∈ [0 ; 10] les couples (2 ; -1) et (10 ; -6) sont solutions.
On a 10 - 2 = 8 et -6 -(-1) = -5. En partant du premier couple, on peut écrire le second de la manière suivante : 2 + 1×8 et -1 + 1×(-5).
Les solutions semblent être de la forme (8k + 2 ; -5k - 1)
On vérifie avec l'équation initiale :
5(8k + 2) + 8(-5k -1) = 40k + 10 -40 k - 8 = 2. Ok !
Les solutions de l'équation sont les couples (8k + 2 ; -5k -1) avec k ∈ ℤ.

Méthode 3 (congruence):

On remarque que 2×8 = 16 et 16 ≡ 1 [5].
On multiplie par 2, l'équation à résoudre devient : 2×5x + 2×8y = 2×2 soit 16y = -10x + 4
Or 10 ≡ 0 [5], 4 ≡ -1 [5] et 16 ≡ 1 [5].
En écrivant la nouvelle équation modulo 5, on arrive à : 1×y ≡ 0 - 1 [5] soit encore y ≡ - 1 [5].
Il existe donc k ∈ ℤ tel que y = 5k - 1.
En reportant dans l'équation simplifiée, on obtient : 5x + 8(5k - 1) = 2 .
Soit 5x = -8×5k + 8 + 2 où encore 5x = -8×5k + 10 et en divisant par 5 on a, x = -8k + 2.
On vérifie avec l'équation initiale :
5(-8k + 2) + 8(5k -1) = -40k + 10 -40k - 8 = 2. Ok !
Les solutions de l'équation sont les couples (-8k + 2 ; 5k -1) avec k ∈ ℤ.

Exemples de résolution d'équations diophantiennes

Exemple 2 : Résoudre l'équation 14x + 20y = 7 où (x ; y) ∈ ℤ².

On vérifie d'abord si l'équation peut admettre des solutions !
On a : 14 = 2×7 et 20 = 4×5 = 2×2×7 donc PGCD(14 ; 20) = 2.
Or 7 n'est pas un multiple de 2, donc l'équation n'admet pas de solutions dans ℤ×ℤ.

Exemple 3 : Résoudre l'équation 59x + 1001y = 1 où (x ; y) ∈ ℤ².

On vérifie d'abord si l'équation peut admettre des solutions !
On a : 59 est un nombre premier et 59×17 = 1003. Par conséquent 1001 ne peut pas être divisible par 59 et PGCD(1001 ; 59) = 1.
L'équation admet donc des solutions dans ℤ×ℤ.

Methode 2 : Avec la calculatrice on dresse un tableau de valeurs de la fonction g(x) =(-1001x + 1)/59...
Attention : Ici x joue le role de y !!!!.
Pour x ∈ [0 ; 100] les couples consécutifs d'entiers relatifs sont (29 ; -492) et (88 ; -1493).
Par conséquent les couples solutions sont (-492 ; 29) et (-1493 ; 88) !!!
On a -1493 - (-492) = -1001 et 88 - 29 = 59. Les solutions semblent être de la forme (-1001k + 492 ; 59k + 29)
On vérifie avec l'équation initiale :
59(-1001k - 492) + 1001(59k +29) = -59×1001k + 59×(-492) + 1001×59k + 1001×29 = -29028 + 29029 = 1 Ok !
Les solutions de l'équation sont les couples (-1001k + 492 ; 59k + 29) avec k ∈ ℤ.

Methode 3 : On a 1001 = 59×17 - 2 donc 30×1001 = 30×59×17 - 30×2. Ainsi, en multipliant par 30, l'équation initiale conduit à :
30×59x + 30×1001y = 30×1 soit 30×59x + (30×59×17 - 30×2)y = 30×1.
En écrivant cette dernière équation modulo 59, on arrive à : -1×y ≡ 30 [59] soit encore y ≡ - 30 [59].
Il existe donc k ∈ ℤ tel que y = 59k - 30.
En reportant dans l'équation initiale, on obtient : 59x + 1001(56k - 30) = 1 .
D'où 59x = -1001×59k + 1001×30 + 1 soit encore 59x = -1001×59k + (59×17 - 2)×30 + 1 c'est-à-dire 59x = -1001×59k + 59×17×30 - 60 + 1.
En divisant par 59 on arrive à : x = -1001k + 510 - 1 soit x = -1001k + 509.
On vérifie avec l'équation initiale :
59(-1001k + 509) + 1001(59k - 30) = -59×1001k + 59×(509) + 1001×59k - 1001×30 = 30031 - 30030 = 1 Ok !
Les solutions de l'équation sont les couples (-1001k + 509 ; 59k - 30) avec k ∈ ℤ.