équation diophantienne

[OY9151]

Noter bien messieurs que je supprime par ce schéma d'OURAGH toutes les tracasseries de et surtout les étourderies de l'algo. de remonté telle que l'on préconise. Pour être exact ce schéma d'OURAGH n'est en fait qu'un procédé optimal (du moins jusqu'à ce jour) synthétisant l'algorithme d'Euclide étendu. De plus chacun notera le format que j'utilise: un tableau à trois ligne uniquement.
Salutations.

[paquito]

Effectivement, ça à l'air efficace, mais ça me fait penser à la méthode de Horner Qui permet de calculer P(a) avec une très grande vitesse, mais les élèves qui voit ce petit tableau de 2 lignes ne comprennent strictement rien; il en est de même pour votre méthode car je ne vois pas tu tout la logique pour l'instant.
Salutations.

[zygomatique]

Pour le second exemple je rappelle que j'ai obtenu

.....542......397.....145.....107.....38....31... .7....3.... (1)
..................1.........2........1.......2.... ..1....4.....2
tableau que je complète comme suite

.....542......397.....145.....107.....38......31... .7....3.... (1)
.................-1.......-2......-1......-2.... .-1.... -4..-2
................-157....115.....-42.....31....-11.....9...-2......1

A partir de ce tableau je relève comme solution particulière (en moins d'une minute à partir du premier tableau) (115,-157) pour l'équation 542x+397y=1 .

J'attends bien vos commentaires Messieurs.
Merci.

des problèmes de connexion ....

peux-tu nous expliquer la construction de ta 3e ligne ?
et pourquoi tu prends les opposés sur la deuxième ligne ?

ensuite finalement nous proposer complètement ton procédé ... puisque tu es lancé :we:

maintenant je ne pense pas que ton procédé diffèrent du principe général ... par contre que tu aies trouvé éventuellement une organisation efficace pour la résolution pourquoi pas ?

ainsi la multiplication à la russe consiste à ne faire que des divisions et multiplications par 2 et est très efficace ....
voir http://fr.wikipedia.org/wiki/Technique_de_multiplication_dite_russe

[zygomatique]

Bonjour,
j'ai juste un aperçu de votre méthode; mai comment remonte t'on les calculs?
Personnellement je procède ainsi:

155=339-184[RIGHT]155=a-b[/RIGHT]

29=184-155[RIGHT]29=b-(a-b)=-a+2b[/RIGHT]

10=155-5*29[RIGHT]10=(a-b)-5*(-a+2b)=6a-11b[/RIGHT]

9=29-2*10[RIGHT]9=(-a+2b)-2*(6a-11b)=-13a+24b[/RIGHT]

1=10-9[RIGHT]1=(6a-11b)-(-13a+24b)=19a-35b[/RIGHT]

voilà, en gros, on présente le calcul comme ça et ça ne se passe pas trop mal.

je rappelle que l'objectif est de trouver une (parmi l'infinité) solution ...

je te mets en parallèle ma méthode et te ferais qq commentaires ensuite

184x + 339y = 184(x + y) + 155y = 29(x + y) + 155(x + 2y) = 29(6x + 11y) + 10(x + 2y) = -(6x + 11y) + 10(19x +35y) = 2

il me suffit de choisir

19x + 35y = 0
6x + 11y = -2

on remarquera à nouveau que le déterminant du système est -1 qui est inversible dans Z donc le système admet une solution entière (x, y) = (-70, 38)

1/ tu peux remarquer donc ainsi l'analogie avec tes égalités de ta colonne de droite
2/ en gros je fais la remontée dans la descente !!!
3/ on veut une solution donc je m'arrête dès que (je vois que) je peux avoir une solution ce qui m'évite de faire la descente complète
4/ tout comme OY9151 ce n'est qu'une façon de présenter/rédiger la méthode

donc tout le monde fait pareil mais ne le présente pas pareil et va plus ou moins loin ou saute certaines étapes par sa façon d'organiser les choses ....

:lol3:

[paquito]

Est ce que ça va plus vite en base 2; ça m'étonnerais! Sinon la méthode serait connu depuis longtemps; déjà, écrie 339 en base 2, il faut le faire à la main, sauf si on a une calculatrice qui le fait; et après? Sinon une méthode non expliquée ne vaut rien et sur le plan pédagogique moins que rien! :triste:

[zygomatique]

Est ce que ça va plus vite en base 2; ça m'étonnerais! Sinon la méthode serait connu depuis longtemps; déjà, écrie 339 en base 2, il faut le faire à la main, sauf si on a une calculatrice qui le fait; et après? Sinon une méthode non expliquée ne vaut rien et sur le plan pédagogique moins que rien! :triste:

qu'est ce que cette histoire de base 2 ?


"sinon une méthode ..."

il n'est pas nécessaire de se faire expliquer une méthode pour l'apprendre il est nécessaire de la comprendre ... mais cela nécessite un minimum de savoir éventuellement ....

le mathématicien indien BHaskara démontre ainsi le théorème de Pythagore en écrivant simplement en dessous de son dessin "regardez !!"

:lol3:

[paquito]

qu'est ce que cette histoire de base 2 ?

c"est toi qui en a parlé; division à la russe! on divise par 2; si c'est pas du binaire....

[zygomatique]

alors va voir sur internet ....

[fatal_error]

alors va voir sur internet ....

que d'agressivité :hum:

http://www.pedagonet.com/videos/egyptienne.html

il est dit que mult à la russe est également appelé méthode égyptienne qui est détaillée ci dessus...
et dans la méthode il est dit de prendre les nombres tels que la somme fait 43.
les nombres choisis corespondent à la décomp de 43 en binaire

mais bon, de tout façon ca c'est de la micro optimisation et pire encore on sait même pas ce qu'on optimise, parce que niveau vitesse de calculs (sur machine), je crois que ya eu pas mal de recherche dessus, et niveau optimisation pour un élève, ben faut définir si c'est le nombre d'étapes et si oui c'est quoi une étape...etc

on peut toujours comparer des méthodes, apprendre des variantes etc, mais de là à dire "j'ai une méthode overkill" ya une énorme marge :we:

[zygomatique]

aucune agressivité de ma part .... tout au plus une réponse lapidaire ....

:lol3:

[OY9151]

Bonsoir tout le monde,

M. Zygomatique pour le 3ème ou la 4ème fois j'affirme que votre idée qui consiste à ramener la recherche d'une solution particulière à celle d'une résolution d'un système de deux équations linéaires est excellente mais je regrette de le répéter que pratiquement ce couple d'équations n'est pas aussi facile à obtenir pour l'instant. Je n'exclu pas que je me trompe et même dans ce cas je ne crois pas qu'il peut y avoir deux élèves de la terminale qui puissent résoudre le système
. . . . . . . . . . . . . . . . . . . 87x+32y=-1 ; . . . . . 19x+7y=3
en moins de 1mn (ceci dit je n'exclu pas une exception!!!). D'ailleurs j'aimerai bien que certains d'entre eux qui nous suivent s'il est possible qu'ils nous le disent en résolvant ce systèmes et s'ils veulent bien nous communiquer le temps qui aura nécessité cela. Je reprendrais le fil de cette discussion une fois que j'aurai une réponse à cette question.
Salutations .

Nb. : que soit remercié d'avance chaque élève pour sa réponse.

[OY9151]

Bonjour,
Monsieur Fatal error si je prends l'exemple qui a été cité par M.Paquito c'est à dire le Schéma de HORNER si je suis votre raisonnement il faut refuser de nommer cette méthode par " Schéma de HORNER " car on risquerai d'affirmer qu'il n'a rien fait de plus ce que RUFFINI avait présenté 20 ans avant lui : effectuer une division euclidienne d'un polynôme Pn(x) par (x-a) sur un tableau à trois lignes. Et pourtant il a le mérite de remarquer que dans ce tableau le dernier nombre calculé n'est autre que Pn(a) et qu'il a justifié par la simple relation Pn(x)=(x-a)Q(x)+R ( Q quotient , R reste). Enfin j'affirme aujourd'hui que ma méthode est une nouvelle méthode synthétique de l'algorithme d'Euclide étendu plus rapide que celles préconisées à ce jour. Je sais on me dira il ne suffit de le dire mais le démontrer effectivement: cela je suis en voie de le faire et bientôt je vous indiquerai le lieu où chacun pourra le vérifié. Pour l'instant retenait uniquement ceci : " SCHEMA D'OURAGH ". Salutations.

[Ben314]

(re)Salut OY9151,
Sans vouloir te vexer, je pense que ta méthode n'apporte pas vraiment quelque chose de nouveau :

1) Je me rapelle que quand j'était au Lycée (donc... il y a fort longtemps...) on voyait les deux méthodes : celle consistant à ne faire qu'une "descente" en calculant au fûr et à mesure les coeff. qu'on doit mettre devant le a et le b pour obtenir le n-ième reste (celle que j'utilise un peu plus haut), ET on voyait aussi celle que tu préconise consistant à ne calculer que les quotients/restes lors de la "descente" puis à "remonter" pour trouver les coeffs à mettre devant le a et le b pour obtenir le pgcd (ou tout autre multiple du pgcd). Si tu cherche sur le Net, tu trouvera plusieurs sites utilisant cette méthode "descente + remontée". Par exemple c'est celle présentée ICI

2) Bien que demandant (trés légèrement) moins de calculs, la méthode "descente + remontée" est petit à petit tombée en désuétude du fait de l'apparition des calculettes/ordinateurs car elle ne représente pas réellement un "mieux" au sens de la complexité informatique :
- L'économie de calcul est trés faible vu qu'on doit quand même calculer les quotients et restes successifs et que le seul "mieux" réside dans le fait que, lors de la "remonté", on a une seule ligne de calcul en plus alors que la méthode "pure descente" demande 2 lignes suplémentaires
- Trés gros inconvénient de la méthode (expliquant sa désuétude à mon avis) : il faut mémoriser lors de la "descente" tout les quotients successifs dans un tableau (informatique) pour pouvoir les réutiliser lors de la "remontée" alors que la méthode "descente uniquement" se fait sans utiliser autre chose que des variables "simples (voir ICI par exemple)

[paquito]

Bonjour,
Monsieur Fatal error si je prends l'exemple qui a été cité par M.Paquito c'est à dire le Schéma de HORNER si je suis votre raisonnement il faut refuser de nommer cette méthode par " Schéma de HORNER " car on risquerai d'affirmer qu'il n'a rien fait de plus ce que RUFFINI avait présenté 20 ans avant lui : effectuer une division euclidienne d'un polynôme Pn(x) par (x-a) sur un tableau à trois lignes. Et pourtant il a le mérite de remarquer que dans ce tableau le dernier nombre calculé n'est autre que Pn(a) et qu'il a justifié par la simple relation Pn(x)=(x-a)Q(x)+R ( Q quotient , R reste). Enfin j'affirme aujourd'hui que ma méthode est une nouvelle méthode synthétique de l'algorithme d'Euclide étendu plus rapide que celles préconisées à ce jour. Je sais on me dira il ne suffit de le dire mais le démontrer effectivement: cela je suis en voie de le faire et bientôt je vous indiquerai le lieu où chacun pourra le vérifié. Pour l'instant retenait uniquement ceci : " SCHEMA D'OURAGH ". Salutations.

La méthode de Horner a déjà le mérite de pouvoir être justifiée:
Si l'on veut: , on obtient:






d'où



, ce qui justifie la méthode et pour ceux qui ne seraient pas convaincu que

; on a

Donc, on donnait cette méthode aux élèves car elle était géniale;

Si et, on obtenait en 3 multiplications et 3 additions

... 3....2....3....-4.....5
...........2....9.....23...74, soit et

Donc cette méthode très facile à utiliser apporte vraiment quelque chose; ce n'est pas une simple variante de la division Euclidienne!!

[Ben314]

...Donc, on donnait cette méthode aux élèves car elle était géniale...
Donc cette méthode très facile à utiliser apporte vraiment quelque chose; ce n'est pas une simple variante de la division Euclidienne!!

Perso, je suis pas super convaincu...
A mon époque, j'en ai jamais entendu parler (et je m'en passait trés bien...) et si tu regarde les différents calculs que l'on fait dans un cas concret (multiplications, additions, soustractions) avec la "méthode de Horner" et que tu compare avec les calculs faits lors d'une division euclidienne, ben il me semble bien que c'est trés précisément les mêmes...

Le seul truc que tu gagne, c'est... un peu d'encre vu que tu n'écris que les coeffs devant les différents X^n sans écrires les X^n eux-mêmes.

[paquito]

Perso, je suis pas super convaincu...
A mon époque, j'en ai jamais entendu parler (et je m'en passait trés bien...) et si tu regarde les différents calculs que l'on fait dans un cas concret (multiplications, additions, soustractions) avec la "méthode de Horner" et que tu compare avec les calculs faits lors d'une division euclidienne, ben il me semble bien que c'est trés précisément les mêmes...

Le seul truc que tu gagne, c'est... un peu d'encre vu que tu n'écris que les coeffs devant les différents X^n sans écrires les X^n eux-mêmes.

pour un polynome de degré 3, tu n'écris que 6 nombres et les trois autres viennent en 3 opérations; en plus la méthode de horner est bien sûr celle qui est utilisée sur le plan informatique:exemple; soit P(x)=4x^3-15x^2+31x-23; calculer P(4): il faut 15 opérations. Passons à la méthode de Horner

...4....4....-15....31....-23
........4......1......35.....117. 6 opérations pour avoir P(4)=117 et en prime P(x)=4x^3-15x^2+31x-23=(x-4)(x^2+x+35)+117

Je ne cherche même pas le nombre d'opérations et de caractéres à utiliser pour la division euclidienne, il n'y a pas photo! tout ça pour dire qu'il y a des méthodes très efficaces pour minimiser le nombre d'opérations et quelles sont bien sûr privilégiées sur le plan informatique, mais ce qui nous est proposé pour Bezout relève du charlatanisme!

[Ben314]

...Je ne cherche même pas le nombre d'opérations et de caractéres à utiliser pour la division euclidienne, il n'y a pas photo!...

Non, il n'y a effectivement "pas photo"....
FAIT LE et... tu verra...

Edit : et si tu ne sait vraiment pas quoi faire, tu peut aussi essayer de calculer le pgcd(141,27) avec les deux méthodes exposées çi dessus pour voir si, comme dans le cas HornerDivision_euclidienne, ce sont trés exactement les même opérations que l'on fait... ou pas => Réponse : NON
Bilan : s'il y a un des d'eux qui doit mériter le terme de "charlatanisme", j'ai bien peur que...

[paquito]

Non, il n'y a effectivement "pas photo"....
FAIT LE et... tu verra...

Edit : et si tu ne sait vraiment pas quoi faire, tu peut aussi essayer de calculer le pgcd(141,27) avec les deux méthodes exposées çi dessus pour voir si, comme dans le cas HornerDivision_euclidienne, ce sont trés exactement les même opérations que l'on fait... ou pas => Réponse : NON
Bilan : s'il y a un des d'eux qui doit mériter le terme de "charlatanisme", j'ai bien peur que...

Pourquoi la méthode d'Horner est celle qui est utilisée en informatique? Charlatanisme?Soit à diviser x^2+3x-2 par x-1: division euclidienne: x(x-1)=x^2-x, d'où x^2+3x-2 -(x^2-x)=4x-2, puis 4(x-1)=(4x-4) et 4x-2-(4x-4)=2, ouf.
et
Méthode d'Horner:

...1....1.....3.....-2
.........1....4......2. donc P(1)=2 et P(X)=(x-1)(x-4)+2 ; 2 multiplications et 2 additions; il est clair que plus le degré de P(x) s'accroît, plus la méthode est meilleure.

En fait, tu n'as pas testé cette méthode et tu dis n'importe quoi! En ce qui concerne le charlatanisme, occupe toi du mégalomane qui a commencé par se présenter comme un élève de TS en difficulté et qui voudrait donner son nom à une méthode foireuse qu'il est incapable d'expliquer. Ce mégalo nous a fait perdre un temps fou.

[Ben314]

Bon, ça va, j'ai compris le style... y'a rien à discuter... :cry:

On va résumé en disant que chacun voit du "charlatanisme"... où il peut...

[nodjim]

Je viens de comprendre la méthode de OY9151, et, la forme mise à part, c'est toujours de cette manière que je résous ce genre d'équation diophantienne. Mais bon, ce n'est pas tous les jours qu'on a à faire ce calcul. Cette méthode, on peut la retrouver, mais est ce bien utile pour un usage aussi peu fréquent ? Il est à noter qu'on peut la rentrer dans un tableur, qui donnera immédiatement une solution particulière, mais pas forcément la plus "petite".