Equations diophantiennes

[ComptableDesMaths]

Bonjour,
y a un truc que je ne comprends pas dans ces équations , en remontant l'algorithme d'Euclide on trouve le couple d'équation x= ka +b y=kc +d pour résumer court hors j'ai remarqué qu'il existe d'autre solutions de ce type, comment les trouver et avec quelle méthode? Merci d'avanc e

[zygomatique]

salut

donne un exemple concret ...

[Lostounet]

Salut

Pourrais-tu être un peu plus explicite sur ce qui te pose problème?

Si tu as résolu une équation diophantienne (ax+by=c avec a et b premiers entre eux), alors effectivement tu arrives à exprimer x et y en fonction d'un entier k: il y a une infinité de solutions.
Bien entendu la manière dont tu paramètre ces solutions peut prendre des formes différentes, mais tu trouves quand même les mêmes solutions quelle que soit la méthode utilisée.

Comprends-tu déjà comment on trouve une solution particulière?

[ComptableDesMaths]

12x-7y=1
avec euclide à l'envers je trouve (3;5) couple de solutions engendrant y=12k+5;x=7k+3;
l'exercice me propose une solution sans méthode qui marche,à savoir (-4;-7) et pour solution x=-4+7k , y=-7+12k;
je crois avoir trouvé une méthode pour changer de solutions enlever ou rajouter 7 et 12 au couple (x;y)>(x-7;y-12)
En conclusion il n'existe pas un seul couple de solutions avec k mais une infinité

[Lostounet]

12x-7y=1
avec euclide à l'envers je trouve (3;5) couple de solutions engendrant y=12k+5;x=7k+3;
l'exercice me propose une solution sans méthode qui marche,à savoir (-4;-7) et pour solution x=-4+7k , y=-7+12k;
je crois avoir trouvé une méthode pour changer de solutions enlever ou rajouter 7 et 12 au couple (x;y)>(x-7;y-12)
En conclusion il n'existe pas un seul couple de solutions avec k mais une infinité

C'est ce que je te disais: tu as trouvé
X=7k+3 y=12k+5

Si tu testes pour k=0 jusqu'à k=2 tu as
X=3 et y=5
X=10 et y=17
X=17et y=29


Par contre dans l'énoncé ils ont trouvé
X=-4+7k et y=-7+12k
Si tu testes pour k = 1, jusqu'à k=3
X=3 et y= 5
X=10 et y=17
X=17 et y=29

En fait les deux paramétrisations sont différentes sur la forme (on génère des solutions différentes en prenant un k différent dans ta solution et dans la leur) mais tu as bien toutes les solutions dans les deux cas. Elles sont équivalentes lorsque k décrit l'ensemble des entiers (relatifs).

[Lostounet]

Une manière simple de le prouver est de constater par exemple, pour ton x:
x=7k+3

X-7=7k-4
X=7(k+1)-4

De la forme x=7k'-4 (on retombe sur leur x, en prenant un autre entier k'). On peut aussi raisonner sur les congruences en disant que 3=-4 (mod 7)

[ComptableDesMaths]

Oui on est d'accord mais on ne peut trouver leur couple de solutions en appliquant modulo 7 et 12 qu'après avoir trouvé la solution par inversion de l'algorithme d'Euclide, pas avant?

[ComptableDesMaths]

En l'occurence, on ne peut trouver le couple(-4;-7) qu'en ayant déjà trouver le couple par Euclide (3;5) ou alors il y a une méthode que je ne connais pas qui me permet de trouver directement (-4;-7)

[Lostounet]

Oui on est d'accord mais on ne peut trouver leur couple de solutions en appliquant modulo 7 et 12 qu'après avoir trouvé la solution par inversion de l'algorithme d'Euclide, pas avant?

Désolé mais je n'ai pas compris...
Que veux-tu dire par "appliquant modulo 7 et 12"?

L'algorithme d'Euclide te garantit une méthode pour trouver à tout prix une solution particulière (u;v) à l'équation ax+by=1

Bien sûr cette solution n'est pas vraiment unique. Je peux en trouver une autre que toi..?

[ComptableDesMaths]

alors si on est pas obligé de passer par cette solution particulière donnes-moi une autre méthode

[Ben314]

Salut,

alors si on est pas obligé de passer par cette solution particulière donnes-moi une autre méthode

L'autre méthode (archi archi archi classique en math dans ce type de contexte ou le but est uniquement de trouver UNE solution quelconque), ben ça s'appelle "le flair".
Au niveau purement scolaire, c'est souvent plutôt mal vu (on peut soupçonner que tu as pompé sur le voisin), mais au niveau de la rigueur, y'a absolument rien à redire : pour résoudre ce type d'équation, tu as besoin d'une solution particulière et la façon dont tu l'a trouvé ne change rien à la rigueur de la preuve.
Par exemple là, si tu écrit que "je constate que (-4,-7) est une solution particulière de l'équation", on ne peut pas dire que ton raisonnement "manque de rigueur".

Sinon, une autre façon de dire (quasi) la même chose, c'est que l'algorithme d'Euclide, il y a plusieurs façon de le mener et pas une seule. Dans tout les cas tu fini par trouver une solution (particulière) au système, mais suivant la façon dont tu mène les calculs, ce n'est pas forcément la même (mais ça, je sais pas si c'est malin que je l'écrive vu que l'ambiance actuelle du système scolaire Français, c'est plus de "suivre les recettes à la lettre" que de voir qu'il y a plusieurs façons de procéder)

[zygomatique]

soit comme le dit ben il y a le flair soit il y a la recette ...

ensuite pour revenir à la question d'autres solutions il serait quand bien de voir que :

si ax + by = c alors a(x - kb) + b(y + ka) = c pour tout entier k et de même en changeant k en - k que a(x + kb) + b(y - ka) = c

donc il y a une infinité de solutions et une infinité de façons de les exprimer (dépendant de la solution particulière) et tout le pb est d'en avoir une ...

de la même façon que pour avoir toutes les mesures d'un angle orienté il suffit d'en avoir une et alors toutes les autres s'obtiennent en ajoutant un multiple de 2pi ...


une autre méthode (pas si éloigné de l'algo d'Euclide) :

12x - 7y = 1 <=> 5x - 7(y - x) = 1

donc (en connaissant mes tables de multiplication plutôt qu'ne me fiant qu'à mon seul flair !!)

x = 3
y - x = 2

<=>

x = 3
y = 5

et si je ne connais pas mes tables de multiplication ... ben je continue :

12x - 7y = 1 <=> 5x - 7(y - x) = 1 <=> 5(x - (y - x)) - 2(y - x) = 1 soit 5(2x - y) - 2(y - x) = 1

donc

2x - y = 1
y - x = 2

<=>

2x - (x + 2) = 1
y = x + 2

<=>

x = 3
y = 5

...

[ComptableDesMaths]

Bon, bas je vois que la solution particulière est toujours la même, d'où son nom

[Pseuda]

Bon, bas je vois que la solution particulière est toujours la même, d'où son nom

Bonjour,

Hum, il y a une infinité de solutions particulières, toutes les solutions de l'équation sont des solutions particulières.

Mais il suffit d'en trouver une parmi cette infinité pour pouvoir résoudre ensuite l'équation. Equation dont l'ensemble des solutions a lui-même une infinité d'expressions différentes (fonctions de la solution particulière de laquelle on est parti).

Mais ces ensembles (avec leurs expressions différentes) sont (heureusement) tous égaux

[nodgim]

En fait, il n'y a qu'une seule solution, à condition de préciser que la valeur de x est donnée modulo 12 et la valeur de y modulo 7. Et tu as 2 écritures possibles, la positive et la négative. (par exemple y = 3 ou 7-3= -4 )