Equations congruences

[Dinozzo13]

Bonjour, je viens ce soir pour revoir en détail ce qui concerne la résolution d'équations avec des congruences.

Je commence par un exemple simple :
Résoudre dasn : .
Je dis que donc donc
Réciproquement, si alors et donc .
Jusque là êtes-vous d'accord ?

[pepito-completementchoco]

Bonjour, je viens ce soir pour revoir en détail ce qui concerne la résolution d'équations avec des congruences.

Je commence par un exemple simple :
Résoudre dasn : .
Je dis que donc donc
Réciproquement, si alors et donc .
Jusque là êtes-vous d'accord ?

je comprend pas ton raisonnement,
1) d'abord tu insinue que ?
2)et puis et egale a non?
il te sufirai de trouver l inverse de 35 modulo 4 .

j'ai peu etre pas compris se que tu voulais montrer

[Blueberry]

Pour ma part ça me convient, le raisonnement est juste.
Pour ma part j'aurais écrit :

35x - 4 = 0
35x = 0
36x - x = 0
- x = 0
x = 0

[Dinozzo13]

Pour ma part ça me convient, le raisonnement est juste.
Pour ma part j'aurais écrit :

35x - 4 = 0
35x = 0
36x - x = 0
- x = 0
x = 0

On est pas obligé de montrer la réciproque ?

je comprend pas ton raisonnement,
1) d'abord tu insinue que ?
2)et puis et egale a non?
il te sufirai de trouver l inverse de 35 modulo 4 .

j'ai peu etre pas compris se que tu voulais montrer

Oui, mais 4 étant petit, je pense que ce n'est pas la peine de calculer l'inverse de 35 dans Z/4.
Toutefois, comment aurais-tu fais pour trouver l'inverse 35 dans Z/4Z ?

[pepito-completementchoco]

On est pas obligé de montrer la réciproque ?


Oui, mais 4 étant petit, je pense que ce n'est pas la peine de calculer l'inverse de 35 dans Z/4.
Toutefois, comment aurais-tu fais pour trouver l'inverse 35 dans Z/4Z ?

j arrive au meme resultat ^^

35x = 3x = 0(4)
3 et 4 premier
donc il existe u et v tq 3u+4v=1
donc 3u=1(4)

on multiplie "les deux coter" par u

désoler je ne connaiser pas le tour de passe passe que t as fait, on peut faire ca pour toute les équation q'u on rencontre ?

[Blueberry]

On est pas obligé de montrer la réciproque ?

Non car j'ai raisonné par équivalence (même la multiplication par -1 à la fin.)

[Dinozzo13]

En fait, il s'agit d'un type d'équations particulières où les entiers ne sont pas très gros.
Si on avait eu des congruences mod 137 par exemple, on serait passer par ta méthode.
.

Mais si on veut résoudre cette équation de manière générale, il faudra bien plus qu'un simple tour de passe-passe :++:

[Dinozzo13]

Non car j'ai raisonné par équivalence (même la multiplication par -1 à la fin.)

Sinon, tu saurais calculer l'inverse de 35 dans Z/4Z ?

[Le_chat]

Ben 35, c'est 3, donc une inverse c'est 3...

[Blueberry]

Sinon, tu saurais calculer l'inverse de 35 dans Z/4Z ?

Oui il suffit, puisque 35 et 4 sont premiers entre eux, d'écrire l'égalité de Bezout :

(-1)*35 + 9*4 = 1

modulo 4 cela donne :

(-1)*35 = 1 mod 4

d'où l'inverse de 35 est -1 (modulo 4)

[Dinozzo13]

Ok, prenons maintenant l'équation par exemple.

Après quelque simplification, on obtient .
Donc là, il y a deux solutions.
Soit traiter au cas par cas, soit à l'aide de Bézout.

Mieux vaut-il calculer comme vous l'avez fait ou est-ce mieux d'utiliser les classes d'équivalence ?

[pepito-completementchoco]

Oui il suffit, puisque 35 et 4 sont premiers entre eux, d'écrire l'égalité de Bezout :

(-1)*35 + 9*4 = 1

modulo 4 cela donne :

(-1)*35 = 1 mod 4

d'où l'inverse de 35 est -1 (modulo 4)

exacte , mais fait la congruence sur 35 avant , ca t evite a l avenir de te perdre dans les calcule inutile

[Le_chat]

Ok, prenons maintenant l'équation par exemple.

Après quelque simplification, on obtient .
Donc là, il y a deux solutions.
Soit traiter au cas par cas, soit à l'aide de Bézout.

Mieux vaut-il calculer comme vous l'avez fait ou est-ce mieux d'utiliser les classes d'équivalence ?

Quand on est sur des congruences "petites", c'est super facile de trouver l'inverse des nombres, donc là tu cherches l'inverse de 2, tu multiplies par cette inverse ton équiation et t'as directement x=...

[Dinozzo13]

Tu veux dire qu'en fait lorsque le modulo est petit, on teste toutes les valeurs des restes :
Par ex :
Si on travaille sur des congruences mod 5, on teste et [mod 5].
Mais si on avait 2011 par ex, on aurait dû utiliser Bézout.

[Le_chat]

Je veux dire que pour trouver l'inverse d'un nombre k modulo n, n "petit", on peu le faire à la main en faisant ainsi: on dit que l'inverse de k c'est l'inverse du reste de k modulo n, et ensuite on calcule à la main (ce qui est raisonnable car n est petit) les produits reste*1, reste*2,..., reste*(n-1) et on voit quand est-ce qu'on tombe sur 1 modulo n.


Ceci ne tient bien sur que lorsque l'on est sur que k est inversible modulo n, donc lorsque k et n sont premiers entre eux. ici, comme tes modulo étaient des nombres premiers, on était sur que tout était inversible (sauf 0 bien entendu. )

[Dinozzo13]

Et si admettons, on avait eu , comment aurais-on fait ?

[Doraki]

mod 8, 9x+5 = 0 <=> x+5 = 0 <=> x=3

[Dinozzo13]

Oui, j'ai pris un mauvais exemple :
Si l'on avait eu par exemple , là il aurait fallu revenir à l'algorithme d'Euclide, non ?

[Blueberry]

Oui, j'ai pris un mauvais exemple :
Si l'on avait eu par exemple , là il aurait fallu revenir à l'algorithme d'Euclide, non ?

Sauf que 138 = 2 mod (136) et 2 n'est pas inversible modulo 136 (ils ne sont pas premiers entre eux)

mettons plutôt 3x + 5 = 0 (mod 136)

3x = -5 (136)

on écrit l'égalité de Bezout :

3*(-45) + 136 = 1 donc l'inverse de 3 est -45 (mod 136)

d'où x = (-45)*(-5) (136)

x= 225 (136)

x = 89 (136)

[Skullkid]

Pour ton équation 2x + 96 = 0 (136), elle est simplement équivalente à x = 20 (68) en divisant tout par 2.