équation diophantienne

par **zygomatique** » 20 Oct 2014, 21:05

paquito a écrit:Ca devient compliqué, c'est de la magie! On ne peut pas demander ça à un élève; et si la démarche demande 3 étapes???

où est-ce compliqué ?

et nulle magie non plus !!!

par contre apprendre et savoir que ::

on réduit et simplifie pour résoudre

et à l'envers

on déréduit et désimplifie pour résoudre !!!!!

ce n'est que Bézout sans l'équation ce qui simplifie considérablement les choses car il est inutile de remonter ...

et n'importe quelle équation diophantienne peut se résoudre ainsi .... (pour trouver une solution particulière) ...

:lol3:

par **OY9151** » 20 Oct 2014, 21:48

Monsieur,

"et n'importe quelle équation diophantienne peut se résoudre ainsi"

théoriquement je serais en accord avec vous si l'on arrive à trouver le bon couple d'équations dont les solutions seraient (chacune) dans Z . Pour nous convaincre de votre artifice je vous serais gré de bien vouloir m'initier de la marche à suivre à travers l'exemple que j'ai proposé il y a 15 mn. Merci d'avance.
Si votre artifice marche à tous les coups cela mérite que vous lui attribuez un nom qui vous conviendrez et je serait même heureux d'être le premier à vous féliciter à moins que vous nous renvoyer vers un autre auteur qui à concrétisé cette idée.
Salutations.

par **Ben314** » 21 Oct 2014, 09:19

Salut,
Perso, face à 666x+245y=2, j'utilise l'algo. d'Euclide étendu que je rédige de la façon suivante :
Je pose a=666 et b=245 pour simplifier les notations. On a donc
666 = a
245 = b
69 = 3*245-666 = 3b-a (la division 666/245=2.7 et je prend l'entier le plus proche, c'est à dire 3)
31 = 4*69-245 = 4(3b-a)-b = 11b-4a (la division 245/69=3.55 et je prend l'entier le plus proche, c'est à dire 4)
7 = 69-2*31 = (3b-a)-2(11b-4a) = 7a-19b
3 = 31-4*7 = (11b-4a)-4(7a-19b) = 87b-32a
1 = 7-2*3 = (7a-19b)-2(87b-32a) = 71a-193b

Donc 2 = 142a-386b

par **paquito** » 21 Oct 2014, 11:12

Ben314 a écrit:Salut,
Perso, face à 666x+245y=2, j'utilise l'algo. d'Euclide étendu que je rédige de la façon suivante :
Je pose a=666 et b=245 pour simplifier les notations. On a donc
666 = a
245 = b
69 = 3*245-666 = 3b-a (la division 666/245=2.7 et je prend l'entier le plus proche, c'est à dire 3)
31 = 4*69-245 = 4(3b-a)-b = 11b-4a (la division 245/69=3.55 et je prend l'entier le plus proche, c'est à dire 4)
7 = 69-2*31 = (3b-a)-2(11b-4a) = 7a-19b
3 = 31-4*7 = (11b-4a)-4(7a-19b) = 87b-32a
1 = 7-2*3 = (7a-19b)-2(87b-32a) = 71a-193b

Donc 2 = 142a-386b

Je suis tout à fait d'accord et je pense qu'avec un peu d'entraînement ce n'est pas vraiment difficile.

par **OY9151** » 21 Oct 2014, 12:34

Bonjour à tous;

Pardonner moi M.Paquito de vous en vouloir un peu : à mon avis cela ne suffit pas d'être en accord avec M. Ben134 mais il mérite toutes les félicitations pour cette excellente idée qui consiste à prendre le nombre " p=partie entière de (a/b ) +1 " qui fournit une bonne synthèse de l'algorithme d'Euclide étendu
et réduit pratiquement de moitié le volume de calcul par le procédé classique de remontée.
Je témoignerai chaque fois que cela me donnera l'occasion que je n'ai vu cette démarche pour la première fois que dans ce forum et ce par Ben314 .
A tout lycéen je conseille de prendre note de cette solution modèle qui est proposée par Ben314.
Salutations.

par **paquito** » 21 Oct 2014, 12:37

L'algorithme de zygomatique fonctionne car miraculeusement, (-6,8) vérifie x+y=2 et 4x+3y=0.

Si on considère: 666x+245y=2 un couple solution est (142, -386) et là évidemment , on a pas x+y=2; donc que devient la méthode? faut il faire apparaître on ne sait pas comment 2 relations ax+by et cx+dy qui vérifient ax+by=0 et cx+dy=2.

Si on prend 27x+5y=1; j'essaie de reproduire la méthode:

27x+5y=1<=>22x+5(x+y)=1<=>2(13x+2y)+(x+y)=1, d'où 13x+2y=0 et x+y=1 qui n'a pas de solutions entières, alors qu'en 3 minutes on trouve (-2, 11).

Donc désolé, je n'ai rien compris et pire, je ne vois pas comment justifier tout ça!

Par contre s'il y'a une justification et une démarche méthodique, je suis preneur.

par **Ben314** » 21 Oct 2014, 13:45

Si le but du jeu est de gagner du temps, à la main, on peut conclure avec moins d'étapes en approchant les quotients non pas par des entiers, mais par des fractions "très simples". Par exemple

666 = a
245 = b
666/245=2.71 proche de 2.75=11/4 ce qui incite à continuer avec :
31 = 11*245-4*666 = 11b-4a
245/31=7.90 proche de 8 :
3 = 8*31-245 = 8(11b-4a)-b = 87b-32a
et on termine facilement avec :
1 = 31-10*3 = (11b-4a)-10(87b-32a) = 316a-859b

(mais la solution est moins "optimale")

par **OY9151** » 21 Oct 2014, 17:19

Bonjour,

Attention la solution est correcte car il faut écrire comme solution générale 632+245k et -1718-666k
et il suffit de fixer k=-2 pour retrouver le couple (142 , -386)
Salutations.

par **zygomatique** » 21 Oct 2014, 19:12

OY9151 a écrit:Bonsoir ,
"Ca devient compliqué, c'est de la magie"

Je suis complètement en accord avec Paquito à moins que cela soit démontré pour l'exemple suivant
666x+245y=2
Salutations .

évidemment beaucoup plus long et dans un tel cas je travaillerai éventuellement comme ben314

de toute façon "ma" méthode est bien sur l'algorithme d'Euclide appliquée dans l'équation

666x + 245y = 176x + 245(2x + y) = 176(3x + y) + 69(2x + y) = 38(3x + y) +69(8x + 3y) = 38(11x + 4y) + 31(8x + 3y) = 7(11x + 4y) + 31(19x + 7y) = 7(87x + 32y) + 3(19x + 7y) = 2

je m'arrête là puisque je vois la solution évidente ::

87x + 32y = -1
19x + 7y = 3

x = 7(-1) - 32(3) = -103
7y = 1960

x = -103
y= 280

on remarquera que le déterminant du système est 87 * 7 - 19 * 32 = 1 (seul inversible de Z (avec son opposé bien sur)) (ho Bachet-Bezout) ....

et donc ça marche tout le temps ....

:ptdr:

Edit :: on peut remarquer que dans son dernier post ben314 fait apparaître des valeurs numériques qui apparaissent dans le mien

:lol3:

par **zygomatique** » 21 Oct 2014, 19:17

paquito a écrit:L'algorithme de zygomatique fonctionne car miraculeusement, (-6,8) vérifie x+y=2 et 4x+3y=0.

Si on considère: 666x+245y=2 un couple solution est (142, -386) et là évidemment , on a pas x+y=2; donc que devient la méthode? faut il faire apparaître on ne sait pas comment 2 relations ax+by et cx+dy qui vérifient ax+by=0 et cx+dy=2.

Si on prend 27x+5y=1; j'essaie de reproduire la méthode:

27x+5y=122x+5(x+y)=12(13x+2y)+(x+y)=1, d'où 13x+2y=0 et x+y=1 qui n'a pas de solutions entières, alors qu'en 3 minutes on trouve (-2, 11).

Donc désolé, je n'ai rien compris et pire, je ne vois pas comment justifier tout ça!

Par contre s'il y'a une justification et une démarche méthodique, je suis preneur.

27x + 5y =2x + 5(5x + y) = 1

il suffit de prendre

x = 3
5x + y = -1

x = 3
y = -16

:ptdr:

Edit :: en même pas 1 mn et 60 s ....

:lol3:

par **OY9151** » 21 Oct 2014, 22:23

Bonsoir ,
Je regrette de dire que je ne suis pas du tout convaincu et ce malgré l'idée (excellente que je reconnais et voir même saluer ! ) de générer un couple d'équations linéaires dont la résolution donnerait la solution particulière. Mais obtenir une tel couple n'est pas simple et surtout qui minimiserait le temps de calcul (à la main) : l'avant dernier exemple que vous avez résolu en est la preuve. Lorsque vous citer les nombres utilisés par Ben134 je pense quelle que soit la technique utilisée dans un tel cas une partie où la totalité des nombres 666 , 245 , 176 , 69 , 38 , 31 , 7 , 3 et 1 apparaîtrons dans les calculs et ce pour la simple raison que les 7 derniers de cette suite de nombres ne sont en fait que les restes des divisions euclidiennes successives des nombres 666 ; 245 .
A ce moment de cette discussion je retiendrai comme meilleure démarche celle donnée par Ben134.
Salutations.

par **paquito** » 22 Oct 2014, 12:25

Bonjour,

j'ai testé les différentes méthodes avec 359x+217y=1
359/217 est proche de33/20 et 20a-33b=19

217/19 est proche de 11 et 217-11x19=8=-220a+364b

19/8 est proche de12/5 et 8x12 -5x19=1=-2740a+4533b;

Donc au niveau rapidité, il n'y a pas photo, la méthode de Ben est la meilleure!
Seul inconvénient, suivant les fractions choisies, la solution trouvée est différente.

L'algorithme d'Euclide étendu nécessite 7 étapes, donc c'est au moins deux fois plus long mais donne la solution "minimale" (81, -134) et une erreur d'étourderie est facilement rectifiable.

Quant à la méthode de zygomatique, ce n'est pas du tout plus simple, ni plus rapide. A réserver aux initiés!

En conclusion, je pense que sur le plan pédagogique, l'algorithme d'Euclide a encore de beaux jours devant lui

par **Ben314** » 22 Oct 2014, 14:31

paquito a écrit:En conclusion, je pense que sur le plan pédagogique, l'algorithme d'Euclide a encore de beaux jours devant lui

Sans parler du fait qu'il est très facile à programmer.
Aprés, on peut un peu améliorer l'algorithme en lui faisant prendre "l'entier le plus proche" à la place du "quotient de la division", mais par contre programmer un truc qui prend "une fraction simple proche du quotient", c'est pas évident...

par **zygomatique** » 22 Oct 2014, 17:51

l'algorithme de la division euclidienne n'est qu'un algorithme de la division

parmi toutes les divisions il n'y en a qu'une seule qui soit euclidienne et sa caractérisation est que le reste est inférieur au diviseur

j'aurais très bien pu commencer comme ben314 dans son premier post :

au lieu de partir de la division euclidienne 666 = 245 * 2 + 176 j'aurais pu faire 666 = 245 * 3 - 69 (qui est une division)

j'aurais alors trouvé une autre solution particulière ....

une équation diophantienne admet une infinité de solutions ... et tout le problème est d'en trouver une ... (et il n'y en a pas de "minimale")

comme je l'ai dit j'utilise aussi l'algorithme de la division !!!! et je sais ne pas me limiter à la division euclidienne même si c'est ce que j'ai fait dans mes exemples .... c'est à dire utiliser l'algorithme d'Euclide étendu comme l'appelle ben314

soit la relation 666x + 245y = 2

et considérons dans

le vecteur

on veut que le produit scalaire

REM :: u_1 est en ligne et v_1 est en colonne

on considère alors la matrice

cette matrice est inversible dans

puisque son déterminant 1 l'est et son inverse est la matrice

alors trivialement

voila où est la magie .... simplement être initié comme dirait l'autre .... non simplement le savoir ...

et la matrice M est une division (ici la division euclidienne) appliquée au couple (666, 245)

et ça se programme très simplement puisque ::

-2 = - E(666/245) et 176 = 666 - 2*245 ou encore pour généraliser 666 = 245q + r

on remarquera que l'inverse de la matrice M = (1 0 \\ -q 1) est (1 0 \\ q 1)

quand on divise la première coordonnée par la deuxième

si on divise la deuxième par la première alors la matrice M est (1 -q \\ 0 1) et son inverse est (1 q \\
0 1)

donc il est aisé de créer un algorithme (en divisant toujours la plus grande coordonnée par la plus petite) qui s'arrête lorsque le reste est nul .... (tout comme pour la division euclidienne)

tout la difficulté est de voir et comprendre que je ne fais que la même chose que ben314 ....

et je rappelle qu'en math spé on voit les matrices qui sont au programme ....

...

:ptdr:

par **paquito** » 22 Oct 2014, 18:12

zygomatique a écrit:l'algorithme de la division euclidienne n'est qu'un algorithme de la division

parmi toutes les divisions il n'y en a qu'une seule qui soit euclidienne et sa caractérisation est que le reste est inférieur au diviseur

j'aurais très bien pu commencer comme ben314 dans son premier post :

au lieu de partir de la division euclidienne 666 = 245 * 2 + 176 j'aurais pu faire 666 = 245 * 3 - 69 (qui est une division)

j'aurais alors trouvé une autre solution particulière ....

une équation diophantienne admet une infinité de solutions ... et tout le problème est d'en trouver une ... (et il n'y en a pas de "minimale")

comme je l'ai dit j'utilise aussi l'algorithme de la division !!!! et je sais ne pas me limiter à la division euclidienne même si c'est ce que j'ai fait dans mes exemples .... c'est à dire utiliser l'algorithme d'Euclide étendu comme l'appelle ben314

soit la relation 666x + 245y = 2

et considérons dans le vecteur

on veut que le produit scalaire

REM :: u_1 est en ligne et v_1 est en colonne

on considère alors la matrice

cette matrice est inversible dans puisque son déterminant 1 l'est et son inverse est la matrice

alors trivialement

voila où est la magie .... simplement être initié comme dirait l'autre .... non simplement le savoir ...

et la matrice M est une division (ici la division euclidienne) appliquée au couple (666, 245)

et ça se programme très simplement puisque ::

-2 = - E(666/245) et 176 = 666 - 2*245 ou encore pour généraliser 666 = 245q + r

on remarquera que l'inverse de la matrice M = (1 0 \\ -q 1) est (1 0 \\ q 1)

quand on divise la première coordonnée par la deuxième

si on divise la deuxième par la première alors la matrice M est (1 -q \\ 0 1) et son inverse est (1 q \\
0 1)

donc il est aisé de créer un algorithme (en divisant toujours la plus grande coordonnée par la plus petite) qui s'arrête lorsque le reste est nul .... (tout comme pour la division euclidienne)

tout la difficulté est de voir et comprendre que je ne fais que la même chose que ben314 ....

et je rappelle qu'en math spé on voit les matrices qui sont au programme ....

...

:ptdr:

Toujours la simplicité! Je te rappelle qu'on cherche une solution abordable par un élève de TS option maths, et qu'en plus une solution minimale est définie. Heureusement que tu n'est pas chargé de l'épreuve de maths en TS , sinon il y aurait une vraie révolte!

par **zygomatique** » 22 Oct 2014, 18:48

paquito a écrit:Toujours la simplicité! Je te rappelle qu'on cherche une solution abordable par un élève de TS option maths, et qu'en plus une solution minimale est définie. Heureusement que tu n'est pas chargé de l'épreuve de maths en TS , sinon il y aurait une vraie révolte!

c'est quoi une solution minimale ?

oui j'enseigne en spé math ....

non je ne propose pas cette méthode .... car il faut savoir calculer (et mentalement entre autre)

heureusement qu'on donne le bac à 90% des élèves aussi ... sinon il y aurait une révolte .... pourtant ils ne savent pas lire, écrire, parler, compter, calculer .... mais c'est pas grave .... ils ont leur bac ....

:lol3:

et si tu te mettais sérieusement à lire ce que je te propose et à y réfléchir ...

ce n'est pas si compliqué que cela .... juste une rédaction différente ...

il suffit de connaître les matrices et le produit de matrices ....

par **OY9151** » 22 Oct 2014, 19:02

Bonsoir,
Messieurs Paquito et Zygomatique je crois que tous deux vous avez raison . Pour vous M. Zygomatique je reprends ce j'ai dis : l'idée de transformer le problème de la recherche de la solution particulière en une résolution d'un système de deux équations est excellente. Pour vous M.Paquito la mise on pratique d'une telle est pour l'instant délicate et donc rendrai difficile son utilisation. Mieux encore pour vous rallier je vous affirme que pour l'exemple 359x+217y=1 j'ai retrouvé la solution particulière en moins de 1mn30.
Salutations.

par **zygomatique** » 22 Oct 2014, 19:12

359x + 217y = 142x + 217(x + y) = 142(2x + y) + 75(x + y) = -8(2x + y) + 75(5x + 3y) = -8(-38x - 23y) + 11(5x + 3y) = -8(-43x - 26y) + 3(5x + 3y) = 1

il suffit de choisir

43x + 26y = -1
5x + 3y = 3

....

par **OY9151** » 22 Oct 2014, 19:21

Bonsoir,
mieux encore la recherche de la solution particulière de
* 5058x+1791y=18 qui après simplification par 9 (vu que chacune des constantes est divisible par 9) ne m'a pris que 1mn50s ;
* 27x+5y=1 que 15s (je dis bien 15 secondes)
* 666x+245y=2 que 1mn 40s ;
* 25x+19y=1 que 20s (je dis bien 20 secondes) ;
Salutations.

par **zygomatique** » 22 Oct 2014, 19:43

3*27 = 81 .... 2s et c'est fini ...

puisque 80 est multiple de 5 ...

au plaisir

équation diophantienne

Qui est en ligne