salut

résous déjà l'équation 12x + 31y = 1

puis ensuite 503 = 1 * 503

....

salut

une methode maison avec les congruences :

31 = 7[12]  --> 31y = 7y[12].
12 =0[12] -->   12x=  0[12]

on additionne les deux équations obtenues à droite , soit  12x+31y = 7y[12]  soit puisque  12x+31y  = 503 ;     503=7y[12]  qui s'ecrit aussi 7y=503[12]  et qu'on peut
encor reduire à  7y = 11[12] .

on  sait que  49 = 1[12]  donc  49y =y[12]  (1) , prenons  7y = 11[12] et multiplions membre à membre par 7  ca donne  49y = 77[12] soit aussi 49y= 5[12] (2)

avec (1) et (2) on a  y=5[12]   donc   y = 5+12k   , reste à sortir x  à partir de 12x+31y  = 503 .

12x + 31.(5+12k)= 503     donne x = 29-31k.

12x + 31y = 503

12(x + 3y) - 5y = 503 = 515 - 12

donc

x + 3y = -1
-y = 103

x = 308
y = -103

donc

12x + 31y = 503
12(308) + 31(-103) = 503

12(x - 308) = -31(y + 103)

....

Bonjour,

ll y a des tas de façons de résoudre une équation Diophantienne (= trouver surtout une solution particulière)

opérer par divination (connaitre ses tables de multiplication par 12 et par 31 )
utiliser des changements de variables (équivalent à la 2ème méthode de carpediem par factorisation de tout ce qu'on peut factoriser)
utiliser des congruences (flight)
résoudre directement par les congruences et le calcul d'un inverse modulo m
utiliser l'algorithme d'Euclide pour obtenir une relation de Bézout 12x + 31y = 1 puis multiplier tout par le second membre (1ère méthode de carpediem)
j'en oublie sans doute...

ces deux dernières méthodes sont en fait la formalisation systématique des méthodes "intuitives" précédentes
et donc programmables sur machine.
une machine ne va pas savoir faire des "on remarque que 49 = 1 [12]" de sa propre initiative !! par contre le calcul de l'inverse de 7 modulo 12, ça elle sait faire
et si on y regarde attentivement l'algorithme d'Euclide est dissimulé dans la méthode de carpediem
(et en fait le calcul de l'inverse modulo m ... dans le cas général c'est l'algorithme d'Euclide, le petit théorème de Fermat aussi mais c'est plus compliqué qu'avec l'algorithme d'Euclide)

oui ma deuxième méthode est l'algorithme d'Euclide déguisé ... mais en plus puissant et ce que ne pourra jamais la machine ::

je ne fais pas la division euclidienne mais une division (et évidemment celle qui m'intéresse le plus )

ainsi sur une machine on ne programme qu'une division et donc la division euclidienne 31 = 12 * 2 + 7

mois j'ai préféré la division 31 = 12 * 3 - 5

c'est du même ordre que le "on remarque" de flight ....


on trouve évidemment la même solution avec la division euclidienne ... mais c'est plus long ou plus compliqué dans ce cas particulier ....

c'est vrai qu'une division Euclidienne "dans Z" (a, b, q, r dans Z) modifiée en
a = bq + r, -|b|/2 < r |b|/2 va aller "plus vite" que avec 0 r < b et que des valeurs positives


le principal est d'avoir un "stathme Euclidien" (cet atrocité étant de Bourbaki parait-il) et la division Euclidienne classique n'en est qu'un exemple.

oui tout à fait ... pour l programmation "d'une" division

mais quand on le fait "à la main" l'objectif est de choisir "la meilleure" division, ie celle qui permet d'obtenir simplement une solution particulière ....

Avec du retard merci

J'ai passé du temps à refaire chacune de vos méthodes pour bien piger et j'ai choisi la méthode de Flight que j'ai trouvé assez astucieuse et comme en plus, on a pas vu ce type de résolution en cours, c'est encore plus intéressant.

Merci encore !

c'est toi qui voit ... seulement une astuce n'est pas un principe général ...

"ma" méthode se généralise à tout type d'équation diophantienne .... en moins rigide que "l'algorithme d'Euclide étendu" tout en étant basé sur le même principe ...

elle est beaucoup plus efficace car à chaque étape on effectue "la meilleure division" ....

le problème des "on remarque que" est qu'on peut très bien passer à côté, et que avec des nombres plus grands on peut ne rien remarquer du tout
("on sait que 49 = 1[12]" est un "on remarque que")

donc il faut connaitre aussi et savoir appliquer la méthode générale sans "on remarque que"
sinon on perd du temps à chercher des remarques qu'on ne trouve pas.

par exemple résoudre l'équation x² - 13761x + 27518 = 0

on remarque que 27518 est presque le double de 13761 = 27522, et que la différence entre les deux est 4
par conséquent 2 est une racine évidente de l'équation et donc l'autre est 27518/2 = 13759 (ou bien c'est 13761 - 2, c'est pareil vu que x² - Sx + P = 0, S est la somme des racines et P le produit)
résolution quasiment de tête de cette équation !!!
bien entendu on peut très bien ne rien remarquer du tout et donc il faut savoir le faire avec delta etc...

même chose pour les équations de Diophante.
savoir repérer un cas particulier pour simplifier la résolution peut très bien passer inaperçu
le remarquer est faire preuve d'astuce, de génie même parfois. c'est très bien et c'est éminemment "intéressant"
mais ça n'empêche absolument pas qu'il faut connaitre la méthode générale, pour quand on ne remarque rien du tout.

ici avec la méthode de Flight, cela revient à trouver l'inverse de 7 modulo 12
en l'absence de "on remarque que l'inverse de 7 est 7 parce que 7*7 = 1 [12]" il faudrait savoir trouver l'inverse d'un nombre modulo un autre dans tous les cas de figure ...
ce qui revient justement en pratique (en vrai) à résoudre une équation semblable à celle de départ :
ici une équation de Diophante 7x = 1 + 12k !!! la méthode tourne un petit peu en rond !
la remarque de flight consiste essentiellement à résoudre cette dernière équation par divination
plus exactement parce qu'on connait et qu'on se récite dans sa tête sa table de 7 et ses multiples de 12, et que cela permet d'affirmer ce "on remarque que 7*7 = 1 [12]"


on aboutirait avec d'autres données à une équation du genre :
trouver par quoi il faut multiplier 357 pour obtenir 1 modulo 451 (réponse loin d'être évidente = 427)
flight aurait alors eu du mal à affirmer : "on remarque (ou on sait) que 357*427 = 1 [451] !!"

pourtant nécessaire à une résolution du genre de 357x - 451y = 1234 par les congruences
(dont la plus petite solution est x = 150, y = 116)