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
Answer
$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$.
No comments:
Post a Comment