Généralisation des restes chinois

[psp]

Bonsoir,

J'ai besoin de votre aide, d'après les restes chinois, le système

x = a [m]
x = b [n]

Admet toujours une solution si n et m sont premiers entre eux.
On peut améliorer tout ça en trouvant une condition suffisante mais nécessaire, j'ai trouvé

PGCD(m,n) doit diviser b - a.
D'après Bézout, Il existe u et v tel que um + vn = PGCD(m,n).

Je trouve le couple (u,v), maintenant le problème c'est que je n'arrive pas à reconstituer la classe de x solution du système.

Pour

x=1[6]
x=21[140]
PGCD(6,140) = 2
2 | 20 => (Bézout) 6x + 140 y = 2 3x+70y = 1

-> (x,y) = (-23, 1)

Pouvez vous s'il vous plait faire la dernière étape de manière détaillée ? Dans le livre la correction ne donne que le résultat mais je n'arrive jamais au même, c'est 301 [420]

Merci !!

[Ben314]

Chercher x tel que et
Signifie chercher x tel que avec et
Il faut donc trouver et
tels que ce qui est effectivement possible si et seulement si PGCD(m,n) divise b - a.
Pour trouver et on peut soit tatonner, soit utiliser l'algo. d'euclide "étendu".
Dans ton exemple, a=1, b=21, n=6, m=140 l'équation est donc
soit encore
Tu vient de constater que .
En multipliant par 10, cela donne donc une des solution est (et mais on en a pas besoin)
d'où est une des solutions.
Mais en fait, tout x congru à -1379 modulo ppcm(6,140)=420 convient.
Par exemple marche aussi.

[nodjim]

Bonjour Ben 314. Je suis très heureux de retrouver ici l'âne si brillant qui nous avait appris tant de choses !

[psp]

Merci beaucoup

[Ben314]

Salut Nodjim.
Heureux de mon coté de te relire et de constater que certains (contrairement à moi...) sont resté "fidèle au poste".

[nodjim]

Salut Nodjim.
Heureux de mon coté de te relire et de constater que certains (contrairement à moi...) sont resté "fidèle au poste".

Seulement, pour ma part, des interventions espacées, mais ce site reste ma page d'accueil sur Internet. Je suis aussi assez souvent, quoiqu'un peu en retrait en ce moment, sur le site "Enigmes et prisedetête" qui offre plus de problèmes originaux que celui ci, plus scolaire. Toujours à torturer tes élèves ?

[Ben314]

Ces dernier temps, je ne torturais plus (problèmes de santé), mais je devrais m'y remettre la semaine prochaine...

[nodjim]

Ces dernier temps, je ne torturais plus (problèmes de santé), mais je devrais m'y remettre la semaine prochaine...

J'espère que tu es pleinement rétabli. Je te souhaite une bonne rentrée. N'y va pas trop fort au début tout de même, en Sup/Spé, même les profs sont mis à rude épreuve...