Equation diophantienne et congruence.

[Vlad-Drac]

Bonjour.
(je note = pour dire congrus à)
j'ai l'equation 125x=275[450]
le calcul de 125^450 me donne 25 et la relation de Bezout 125*(-7) + 450*2 = 25
ou 125*(-7) -25 = -2*450
d'ou la congruence:
125*(-7) = 25 [450]
en multipliant par 11 il vient
125*(-77)=275[450]
j'ai conclu x = -77 + 450 k

le probleme c'est que la reponse est S={13+18k}

quelqu'un pourrait il m'expliquer mon erreur ?
merci d'avance

[Black Jack]

Salut,

Avec tous les k entiers :

125x = 275 + 450.k
5x = 11 + 18.k
5x = (11 + 18k') + 18.k"

avec k' = 3 --> 5x = 65 + 18.k"

En posant k" = 5.K

5x = 65 + 90.K
x = 13 + 18K

Mais ce n'est certainement pas comme cela qu'on l'enseigne actuellement.

[Pseuda]

On peut remarquer que l'équation 125x=275[450] est équivalente à l'équation 5x=11[18].

Sinon ton calcul n'a pas de sens, d'où sort la relation avec x à la fin ?

[Vlad-Drac]

On peut remarquer que l'équation 125x=275[450] est équivalente à l'équation 5x=11[18].

Pourquoi a on le droit de simplifier ? ca n'est pas tout le temps vrai ..

[Pseuda]

On a le droit se simplifier parce que tous les nombres sont divisés par 25.

Par exemple, 2x=6 [4] n'est pas équivalent à x=3 [4], mais c'est équivalent à x=3 [2].

[Elias]

Sinon de façon générale, si tu as :
ka = kb (mod kn) (avec a,b,n, k entiers), c'est équivalent à: a=b (mod n).
C'est à dire que l'on peut diviser tout par k à condition de diviser aussi le nombre à l'intérieur du modulo et à condition que tout soit divisible par k.

Tu peux le démontrer facilement en revenant à la définition de la congruence.


Et puis, si tu veux pas diviser le modulo, il faut une condition en plus :

Si ka=kb [n] alors a=b [n] si k et n sont premiers entre eux.
Donc ici, on a divisé par k sans diviser le nombre à l'intérieur du modulo mais on peut le faire si k et n sont premiers entre eux.

En guise d'entrainement, tu peux le montrer à l'aide du théorème de Gauss.

[Ben314]

Salut,

Vos réponses sont équivalentes.
Tu dis que l'ensemble des x qui conviennent sont ceux qui s'écrivent sous la forme x = -77 + 450k avec k entier.
Le corrigé dit que c'est l'ensemble des nombres qui s'écrivent sous la forme 13+18 K avec K entier (j'ai mis un K majuscule pour pas qu'il ait confusion car c'est pas le même k).

Ben... non, c'est pas équivalent.
Par exemple 13, c'est bien un 13+18K (13=13+18x0), mais c'est clairement pas un -77+450k !!!

Bref, j'ai plus que des doute concernant ça :

Réciproquement, on montre de la même façon qu'un entier de la forme 13+18K s'écrit bien sous la forme -77+450k.

j

[Elias]

Oui bien sûr, je suis allé trop vite.


Sinon pour en revenir à l'erreur faite.
De façon générale, tu as l'air de déduire que si ax0 = b [n] (c'est à dire, si l'on a trouvé une solution particulière x0) alors les solutions de ax=b [n] sont exactement les x de la forme x0+nk.

Pas forcément. Bien sûr, les x de la forme x0+nk seront des solutions mais tu ne les auras pas toutes car la réciproque n'est pas vraie.


Si on prend un entier x tel que ax=b [n], alors comme ax0= b [n], on en déduit a(x-x0) = 0 [n] donc n divise a(x-x0)

Et puis on ne peut pas en deduire que n | (x-x0) (ce qui permettrait d'écrire que x=x0+nk). Pour cela il faudrait que n et a soient premiers entre eux.

C'est pour cela d'ailleurs qu'on se ramène à une situation où a et n sont premiers entre eux pour résoudre de telle équations en simplifiant comme Pseuda l'as fait.

[Pseuda]

Bonjour,

Pour se résumer, l'égalité ka=kb [n] peut se simplifier par k dans l'un ou l'autre cas :
- si on divise le modulo en même temps (n est multiple de k)
- k est premier avec le modulo.

Pour le questionneur,
- 1er cas : ka=kb [kp] ssi il existe un entier q tel que ka-kb=kpq ssi a-b=pq ssi a=b [p]
- 2ème cas : ka=kb [n] ssi n | ka-kb = k(a-b), et comme n^k=1, ssi n | (a-b) ssi a=b [n]