Système de congruences

[invite2e8ce3aa]

Bonjour,

Nous sommes en train de faire un exercice sur les congruences, mais on ne comprend pas la correction qu'on a (d'ailleurs, on ne comprend pas non plus comment résoudre l'exercice).

Alors, on a :

1243 _^ 1067 = 11 (paraît que ça peut servir )

On doit trouver x tel que :



Le premier réflexe serait d'utiliser le théorème chinois, mais 1243 et 1067 ne sont pas premiers entre eux.

Dans la correction :
Ils se ramènent au système
(113*11=1243)

avec x = 25 + 11y
Mais d'où vient ce -1 ? (et le système, tant qu'on y est - ça, c'est la patate)

[pour info : suite de la correction]
y = 678 est une solution particulière.
Et les autrse diffèrent par un multiple de 113*97=10961
Les solutions du système initial sont donc x=7483+120571k (et d'où vient 7483 ?)


Mici,



La patate (qui crie "non") et la molette (qui va s'en prendre une)
-----

[invite8be57c24]

Alors, je n'ai pas fait les calculs mais selon moi ce qu'il se passe c'est qu'on divise dans chanque congruence par le pgcd et alors :



Alors là on trouve les inverses de 11 modulo 113 et modulo 97 on fait la multiplication par 25 et 14 modulo 113 et 97
en posant tu te ramènes à l'utilisation tu théorème chinois car 113 et 97 sont premiers entre eux et tu as quelque chose de la forme :


voilà bonne chance

[invite1237a629]

Salut,

En fait, ce qui nous a gênés c'est que dans la correction, ils introduisent un y dont on ne comprend pas trop l'origine, puis certaines données nous semblent bizarres...

Sinon, oui, il est sûrement possible de se ramener à un cas d'utilisation du théorème chinois.
Comme inverse de 11 dans Z/113Z, je trouve -41, ce que je n'arrive toujours pas à expliquer par rapport à la correction
De plus, a-t-on le droit de dire que y=x/11 dans les deux cas, alors que l'inverse de 11 dans Z/97Z n'est pas le même que dans Z/113Z ?

[invite8be57c24]

Salut c'est vrai que la méthode utilisée dans la correction ne me semble pas être la plus naturelle pour trouver le -1 je présume qu'il s'agit de 14*(25*11)^(-1) mudulo 97....
Je pense qu'on à le droit de poser y=x/11 comme je l'ai fait mais c'est sûr que là ce n'est plus le même que celui de votre corrigé !
en fait
et celà revient à
et
d'où en simplifiant pas 11 :
et
et donc en faisant le chemin inverse on retombe sur le système avec y.
j'espère que la démo vous convient mais c'est vrai qu'on est en droit de se demander pourquoi on ne cherche pas l'inverse de 11 modulo 97 et 113 et qu'on le multiplie par x... je pense que les deux systèmes sont équivalents c'est juste qu'on le laisse sous cette forme pour se retrouver dans le cas d'application du théorème chinois !
Si quelqu'un a une explication plus rigoureuse je suis preneur aussi !

[A voir en vidéo sur Futura]

[invite35452583]

On doit trouver x tel que :

De manière générale, soit un système du type :


avec p et q premiers entre eux (ou autrement dit dp^dq=d).
On a en particulier x-a est un multiple de d
et en particulier x-a et b-a sont congrus modulo d
Donc b-a est un multiple de d (b-a=d.c) s'il existe une solution au système.
Dans ce cas on peut poser x-a=dy, autrement dit x=a+dy
Le système devient :


Ce qui revient à



En appliquant au système initial on a x-25=11y (x=25+11y)


Ce qui revient à :


ce qui se résoud par le théorème chinois : y=solution particulière (existe toujours)+113.97k
y=678+10961.k
x=25+11(678+10961.k)=(25+11.67 8)+11.10961.k
x=7483+120571.k

[invite1237a629]

Bonsoir,

Merci infiniment pour ton explication. Tout est beaucoup plus clair ! Serait-ce indiscret de te demander d'où tu tiens cette méthode ? Car aucun de nous deux ne l'avons vue en TD (encore moins en cours) et pourtant la correction sous-entendait qu'on la connaisse...

Ah oui, un point qu'on ne comprend pas (peut-être sur le coup) :

et en particulier x-a et b-a sont congrus modulo d
Donc b-a est un multiple de d (b-a=d.c) s'il existe une solution au système.

Comment peut-on dire que x-a et b-a sont congrus modulo d ?

Edit : ah oui, je vois now...x-a est un multiple de d...


Merci à haruspice également,

[invite35452583]

Comment peut-on dire que x-a et b-a sont congrus modulo d ?

Edit : ah oui, je vois now...x-a est un multiple de d...

Rien à voir avec le fait que x-a soit un multiple de d (on rapproche les deux résultats après)
x-a est congru à b-a modulo d car x-a est congru à b-a modulo dq : [(x-a)-(b-a)]=truc x qd donc égal bazar x d avec bazar=truc x q.

Merci infiniment pour ton explication. Tout est beaucoup plus clair ! Serait-ce indiscret de te demander d'où tu tiens cette méthode ?

Trop ancien pour que je m'en souvienne.

[invite1237a629]

x-a est congru à b-a modulo d car x-a est congru à b-a modulo dq : [(x-a)-(b-a)]=truc x qd donc égal bazar x d

En fait, on pourrait aussi dire que x-a congru à 0 mod pd, donc x-a multiple de d.

x-a congru b-a mod qd => x-a = b-a + qdk
x-a multiple de d, qdk multiple de d, donc b-a multiple de d

Ca marcherait comme ça ?

Oki en fait, je proposais ça parce que je n'avais pas bien saisi certaines choses. Now, ça va :P
Re-édit : je suis repaumée...

J'ai beaucoup de mal avec ce passage :

en particulier x-a et b-a sont congrus modulo d
Donc b-a est un multiple de d (b-a=d.c) s'il existe une solution au système.
Dans ce cas on peut poser x-a=dy, autrement dit x=a+dy

Parce que si j'écris que x-a et b-a sont congrus modulo d, mon premier réflexe est de dire que x-a est un multiple de d, et donc que b-a en est un ~

[invite35452583]

En fait, on pourrait aussi dire que x-a congru à 0 mod pd, donc x-a multiple de d.

x-a congru b-a mod qd => x-a = b-a + qdk
x-a multiple de d, qdk multiple de d, donc b-a multiple de d

Ca marcherait comme ça ?

Oui là tu as compris.

[invite1237a629]

Pourrais-tu expliquer pourquoi tu dis d'abord que b-a est multiple de d, puis x-a l'est, s'il te plaît ?

(suite à l'énième édit de mon post précédent :s)

[invite35452583]

Pourrais-tu expliquer pourquoi tu dis d'abord que b-a est multiple de d, puis x-a l'est, s'il te plaît ?

(suite à l'énième édit de mon post précédent :s)

Dans la rédaction initiale je crois que x-a multiple de d arrive avant.
Mais surtout, c'est que "b-a multiple de d" est une condition nécessaire à l'existence de solution(s). Ce n'est pas la peine de chercher "x" si on sait qu'il n'existe pas.

[invite1237a629]

Ah ok, on allie les hypothèses aux conditions donc...

C'est juste cette inversion de conclusion que je n'avais pas comprise.

Encore merci !


(now, faut que j'arrive à expliquer ça à une patate )