0

I am familiar with finding solution to $ax=b$ in $\mathbb{Z_m}$ , but how could I know whether there is more than 1 solution?

For example solving $83x=2$ in $\mathbb{Z_{321}}$ I have found $x=205$ but is there anymore? like in $2x=4$ where we get $x=2$ or $x=5$ in $\mathbb{Z_6}$. Thanks

user577215664
  • 40,625
Rivaldo
  • 378
  • 1
    note that in $\mathbb{Z}_m$ that if $k \in \mathbb{Z}$ then we have $a(x+km) = ax + akm = ax$. So straight off the bat, if $x$ is a solution then the set ${ x + km | k \in \mathbb{Z} }$ is also a solution – kelly maggs Apr 10 '18 at 01:45

1 Answers1

1

$ax \equiv b \bmod m$ has a solution iff $d=\gcd(a,m)$ divides $b$.

In this case, all solutions come from solving $a'x \equiv b' \bmod m'$, where $a=da'$, $b=db'$, $m=dm'$.

Now, $\gcd(a',m')=1$ and so $a'x \equiv b' \bmod m'$ has exactly one solution $x_0$ mod $m'$, which can be found with the extended Euclidean algorithm.

The original equation thus has exactly $d$ solutions mod $m$, given by $x_0+t m'$, for $t=0,\dots, d-1$.

lhf
  • 216,483