Crypto/arythmétique à nouveau

[Tinoute]

Re bonjour !

j'ai un nouveau problème :
"Calculer le pgcd d de 34177 et 12342. Déterminez l'ensemble (u,v) de Z² tels que 34177u+12342v=d"

j'ai trouvé un couple par l'algorithme étendu d'Euclide : u=-13 et v=36, mais je ne sais plus comment avancer ...

Merci d'avance !

[benekire2]

A quoi ressemble cette équation ?

Tu dois surement connaître des méthodes pour résoudre cela ... maintenant que tu as trouvé un couple solution !!

[Tinoute]

l'équation c'est donc : 36*12342-13*34177=11
Je ne me sens pas trés malin, mais j'arrive pas a aller plus loin ...

Et une autre question : est-ce qu'il existe bien un théorème, lemme, ou autre disant que pour un couple (a,b) donné, il existe (u,v) tq au+bv=d <=> d est un multiple de pgcd(a,b) ???
Si oui, lequel ?

[Ben314]

Pour ta première question, une fois trouvé une solution particulière u0, v0 d'une équation de la forme a.u+b.v=d, tu réécrit ton équation sous la forme :
a.u+b.v=a.u0+b.v0, c'est à dire a(u-u0)=b(v0-v) puis tu divise des deux cotés par le pgcd(a,b) de façon à avoir a'(u-u0)=b'(v0-v) où a' et b' sont premiers entre eux. Enfin tu utilise le "lemme de Gauss" pour dire que, comme a' divise b'(v0-v) on doit avoir a' qui divise v0-v.

Pour ta deuxième question, la réponse est oui (c'est d'ailleurs une des définitions possible du pgcd) mais je ne sais pas si ça porte un nom car ça découle immédiatement du théorème de Bézout :
"Si d=pgcd(a,b) alors il existe u,v tels que au+bv=d"

[Tinoute]

Pour ta deuxième question, la réponse est oui (c'est d'ailleurs une des définitions possible du pgcd) mais je ne sais pas si ça porte un nom car ça découle immédiatement du théorème de Bézout :
"Si d=pgcd(a,b) alors il existe u,v tels que au+bv=d"

Le thm de Bezout est une implication, on peut en conclure l'équivalence
au+bv=d SI ET SEULEMENT SI de est multiple de pgcd(a,b) ?

[ffpower]

Le sens "pas Bezout" est trivial : au+bv est forcément un multiple de pgcd(a,b)..

[Tinoute]

Pour ta première question, une fois trouvé une solution particulière u0, v0 d'une équation de la forme a.u+b.v=d, tu réécrit ton équation sous la forme :
a.u+b.v=a.u0+b.v0, c'est à dire a(u-u0)=b(v0-v) puis tu divise des deux cotés par le pgcd(a,b) de façon à avoir a'(u-u0)=b'(v0-v) où a' et b' sont premiers entre eux. Enfin tu utilise le "lemme de Gauss" pour dire que, comme a' divise b'(v0-v) on doit avoir a' qui divise v0-v.

le fait que a' divise v0-v est une condition nécessaire, mais pas suffisante, je cherche l'ensemble des couples donc je voudrais une condition nécessaire ET suffisante ...

[Tinoute]

Je sais que c'est pas super d'insister, mais la je sèche vraiment...
Il faut que a' divise (v0-v) et b' divise (u-u0) (ou bien que v=v0 ret u=u0), mais ca ne suffit pas (si je garde u0 mais que je rajoute a' à v0, les conditions sont respectées, mais le couple ne convient pas ...) :mur:
Une idée pour avoir mon ensemble de solutions ???

[Ben314]

Bon, on en était (par équivalence) à :
a'(u-u0)=b'(v0-v) [*] avec a' et b' premiers entre eux.
Comme a' divise b'(v0-v) on doit avoir a' qui divise v0-v : tu as raison, ce n'est qu'une implication, mais cela permet d'affirmer que v0-v=k.a' pour un certain k dans Z.
Maintenant que l'on a cette relation, on la réinjecte dans l'équation [*] :

[*] devient équivalente à a'(u-u0)=b'.k.a', c'est à dire à u-u0=k.b'.
Les solutions sont donc les u=u0+k.b' et v=v0-k.a' avec k dans Z.