Equations diophantiennes

[LaFouine94]

Bonjour,
J'ai récupéré le solveur d'équations diophantiennes d'Adriweb, mais je suis embêté par sa rédaction, car il invoque le théorème de Gauss, même si les deux entiers ne sont pas premiers entre eux.
Exemple :

Code: Select all

diophant(15,21,318)
Résolution de 15*x+21*y  =  318
Solution évidente :  {10,8}
15*x+21*y  =  15 * 10  +  21 * 8
15 ( x-10 )  =  −21 ( y-8 )
15  divise  −21 ( y-8 )  (Gauss)
->  y-8  =  15 ·k
✓  y=15*k+8
->  15*(x-10)  =  −21 ·( 15 k)
->  x-10  =  −21 ·k
✓  x=10-21*k
Solutions :  {x=10-21*k,y=15*k+8}

On ne peut pas passer de 15 divise -21(y-8) à 15 divise y-8 en invoquant Gauss puisque 15 et 21 ne sont pas premiers entre eux.
Il faudrait commencer la rédaction en calculant le PGCD de 15 et 21 et en divisant toute l'équation par ce PGCD.
Qu'en pensez-vous ?

Merci
LaFouine94

[Bisam]

Tu as parfaitement raison... et du coup la solution d'Adriweb est fausse, dans ce cas.

[Adriweb]

Ouai, effectivement (personne ne l'a remarque en plusieurs annees ? ) - la justification est fausse, mais la solution est bonne (brute force ).
Cf. la version de Laurae qui fait les choses un peu moins a l'arrache.

[Bisam]

La solution évidente est juste, mais la solution finale est fausse !

L'ensemble des solutions est en fait :

$mathjax$\{(10-7k, 8+5k), k\in\mathbb{Z}\}$mathjax$

[Opaline6]

Bonjour,
Pourriez vous si possible m'envoyer le programme que vous avez pour résoudre des équations diophantiennes s'il vous plait ? Cela pourrait m'être bien utile pour mon bac mercredi