un système

[invite371ae0af]

bonjour,

j'ai un système chinois à résoudre:

x=192 mod517
x=311 mod697
x=507 mod667

le résultat est x= 261 mod(517x697x667)

mes questions sont:

comment vérifier que le x que je trouve est juste?

y-a-t-il une autre méthode plus rapide pour trouver x que celle qui consiste à :
x=192+517k je remet dans la seconde équation puis je chercher l'inverse et ainsi de suite


merci de votre aide
-----

[sylvainc2]

Ta réponse n'est certainement pas bonne, car 261 n'est pas congru à 192 mod 517. La bonne réponse est x=27,000,000 (27 millions).

Je ne connais pas ta méthode, mais pour la trouver je fais comme ceci:

1ère congruence: 697*667 = 464,899
On cherche k1 tel que 464899 k1 = 192 mod 517
--> k1 = 192 * 464899^-1 = 192 * 166^-1 mod 517 car 464899=116 mod 517
k1 = 192 * 156 = 29,952 = 483 mod 517 car 166^-1 = 156 mod 517
Donc x1 = 464899 * 483 = 224,546,217

2è: 517*667 = 344,839.
On cherche k2 tel que 344,839 k2 = 311 mod 697
--> k2 = 311 * 344,839^-1 = 311 * 525^-1 = 311 * 99 = 30,789 = 121 mod 697 (car 344,839=525 et 525^-1 = 99 mod 697)
Donc x2 = 344,839 * 121 = 41,725,519

3è: 517*697 = 360,349
On cherche k3 tel que 360,349 k3 = 507 mod 667
--> k3 = 507 * 360,349^-1 = 507 * 169^-1 = 507 * 371 = 188,097 = 3 mod 667 (car 360,349=169 et 169^-1 = 371 mod 667)
Donc x3 = 360,349 * 3 = 1,081,047

La solution est x=x1+x2+x3 = 267,352,783 = 27,000,000 mod (517*697*667)

Je ne pense pas qu'il y ait de méthode plus rapide que ca. Il faut calculer des inverses, et avec ces nombres ca donne de gros calculs à faire mais on n'a pas le choix.

[invite371ae0af]

merci de ton aide
effectivement la méthode avec les inverses est la mieux