congruenze

[aleida]

qualcuno mi saprebbe dire nel dettaglio come si risolve la congruenza:
ax = b mod n

dove ho impropriamente usato = con il significato di congruo.
grazie

[frodo4]

Cerca l'inverso di a mod n, quindi la congruenza si riduce a $x-=c mod n$, con $c=a^-1b$, a quel punto la soluzione è data da $x=c + nk$, con $k in ZZ$.
Oppure sapendo che $a$ e $b$ sono congurenti mod $n$ se $a-b=kn$, risolvere la congruenza si riduce a risolvere l'equazione diofantea $ax-kn=b$.

[Lord K]

Beh in ogni caso il procedimento di frodo4 è corretto sempre se $a$ un inverso ce lo ha davvero.... altrimenti la soluzione diventa solo di poco differente.

Si dimostra, infatti, che se $gcd(a,n)=1$ allora ovviamente $a$ risulta invertibile! (Discende direttamente dal $gcd$)

Se così non è e se $gcd(a,n)=d$ allora la congruenza da risolvere diventa:

$(a/d)x -= b (mod(n/d))$

ove si procede come ha specificato frodo4.