Résolution d'une équation sur la congruence

[Don vito]

Salut,
Pourriez vous s'il vous plait m'expliquer comment l'on résout une équation du type : ax ;) b (mod n) , je m’intéresse surtout au cas ou n est premier.J'ai lu quelque chose dessus , un exemple pour préciser: 3x;) 5 (mod 7) , ils disent après que 3^(-1);)5 (mod 7) , je me pers un peu.( je voudrais signaler ...sans éclater l'écriture càd se ramener à une equ de premier degrés)

Merci

[Le_chat]

Salut. Une idée ici, comme la méthode suggérée dans ton exemple, est de trouver l'inverse de a "modulo n" c'est à dire d'essayer de trouver un nombre c tel que a*c=1 modulo n.

Théoriquement, on sait que c'est toujours possible lorsque n est premier (sauf si, bien entendu, a=0).

En pratique il doit y avoir des méthodes pour trouver l'inverse, je n'en connais pas trop, ptete que d'autres personnes pourront t'éclairer.

Et une fois qu'on a trouvé l'inverse de a, c, on a:

ax=b modulo n si et seulement si c*a*x=b*c modulo n, si et seulement si x=bc modulo n, donc tu trouves une infinité de solutions, tous les entiers congrus à bc modulo n!

Comme il est courant de noter l'inverse avec un "^-1", on s'autorise à noter c=a^-1, donc dans ton exemple, modulo 7, 3^-1=5, ce qui se vérifie car 3*5=15, ce qui fait 1 modulo 7.

[Don vito]

Parfait!Merci beaucoup Le_Chat.ça fait bien longtemps que j'ai plus retouché l'arithmétique , quant aux opérations pourriez s'il vous plait me rappeler le cas ou le modulo se voit modifié par une multiplication quelque chose du genre?
Merci encore

[Skullkid]

Bonsoir, pour trouver l'inverse de a modulo n, une méthode est d'appliquer l'algorithme d'Euclide pour trouver le pgcd de a et n (si n est premier on sait déjà que ce pgcd vaut 1, mais peu importe). L'algorithme fournit une identité de Bézout au + nv = d avec d le pgcd de a et n. Si d est différent de 1, a n'est pas inversible modulo n. Si d vaut 1, u (enfin, la classe de u modulo n) est l'inverse de a modulo n.