Algorithme d'Euclide et entiers relatifs

[upium666]

Bonjour à tous et à toutes !

J'ai un problème en voulant résoudre des équations diophantiennes du type : ax-by=c ou ax+by=-c ou ax-by=-c puisque pour trouver une solution particulière, je procède en appliquant l'algorithme d'Euclide, mais pour les nombres entiers relatifs, cela pose problème

Comment résoudre alors des équations diophantiennes telles que 17x-33y=1 ?

Merci

[Sourire_banane]

Bonjour à tous et à toutes !

J'ai un problème en voulant résoudre des équations diophantiennes du type : ax-by=c ou ax+by=-c ou ax-by=-c puisque pour trouver une solution particulière, je procède en appliquant l'algorithme d'Euclide, mais pour les nombres entiers relatifs, cela pose problème

Comment résoudre alors des équations diophantiennes telles que 17x-33y=1 ?

Merci

Salut,

En général on cherche de vue si des solutions immédiates viennent à l'esprit. En dernier recours on utilisera l'algo étendu d'Euclide.

Le but c'est de chercher à diviser -33 par 17. Pour cela, tu écris la div euclidienne, normal, et en partant de 1 tu dois remonter l'algo pour arriver à une combinaison linéaire faisant intervenir 17 et -33 avec des coefficients qui seront tes solutions particulières.
Ici c'est très simple. On obtient x0=2 et y0=1

[upium666]

Salut,

En général on cherche de vue si des solutions immédiates viennent à l'esprit. En dernier recours on utilisera l'algo étendu d'Euclide.

Le but c'est de chercher à diviser -33 par 17. Pour cela, tu écris la div euclidienne, normal, et en partant de 1 tu dois remonter l'algo pour arriver à une combinaison linéaire faisant intervenir 17 et -33 avec des coefficients qui seront tes solutions particulières.
Ici c'est très simple. On obtient x0=2 et y0=1

D'accord, mais comment faire une division euclidienne avec des entiers relatifs ? Dans notre cours, nous n'avons abordé que les divisions euclidiennes entre des entiers naturels, ce qui n'a nécessité ni q négatif, ni b négatif, etc...

[Ben314]

D'accord, mais comment faire une division euclidienne avec des entiers relatifs ? Dans notre cours, nous n'avons abordé que les divisions euclidiennes entre des entiers naturels, ce qui n'a nécessité ni q négatif, ni b négatif, etc...

Que tes nombres soient positifs ou négatif ne change absolument rien.
Par exemple, dire que (x,y) est solution de 25x-37y=-18 (avec des négatif), c'est clairement la même chose que de dire que (-x,y) est solution de 25x+37y=+18 (avec que des positifs)

Donc pour ne pas te faire c..., ton algo. d'euclide, tu le fait systématiquement avec des nombres positifs et, à la fin, tu change (éventuellement) le signe des solutions trouvées.

Par exemple, l'algo d'euclide avec 17 et 33 te donne comme pgcd 1 et te permet de voir que :
17x2 + 33x(-1) = 1
Et ç'est pas bien sorcier d'en déduire que
17x2-33x1 = 1
ou bien que
33x(-1)-17x(-2) = 1
ou encore que
-33x1 - 17x(-2) = 1