I want to solve $ax \equiv b \mod n$ given a solution $x_0$. How can i prove that there are exactly $(a,n)$ solutions ?
Number of solutions of $ax \equiv b \mod n$
-
0http://en.wikipedia.org/wiki/Linear_congruence_theorem – 2013-10-27
2 Answers
Suppose $x$ is a soloution, then $a(x-x_0)\equiv 0$ mod $n$. Hence $a(x-x_0)=nk$ for some integer $k$, that is $x=x_0+\frac{nk}{a}$. Suppose $d=(a,n)$ and $a=db,n=dm,(b,m)=1$. Then you have $x=x_0+\frac{dmk}{db}=x_0+\frac{mk}{b}$ This implies $b|mk$ but $(b,m)=1$, hence $b|k$. So one can write $x=x_o+\frac{nk}{db}=x_0+\frac{n(k/b)}{d}$ So every soloution is of the form $x_0+\frac{nt}{d}$ and you can easily check that $x_0+\frac{nt}{d}$ is indeed a soloution for all integer $t$. Now observe that for $t\geq d$ the same soloutions for $t=0,\ldots d-1 $ are repeated. Now to prove that these are the only soloutions assume $x_0-\frac{nt_1}{d}=x_0+\frac{nt_2}{d}$ where $0\leq t_1
Hint $\ $ Let $\rm\:c = x_0.\:$ Working $\rm\:mod\ n,\:$ if $\rm\:ac \equiv b\:$ then $\rm\:ax\equiv b\iff ax\equiv ac\iff n\mid a(x - c).\:$ Denote the gcd $\rm\:d = (n,a) = d(\bar n,\bar a)\:$ for $\rm\:\bar n = n/d,\ \bar a = a/d,\:$ and $\rm\:\color{#0A0}{(\bar n,\bar a) = 1}.\:$ Then, canceling $\rm\,d,$
$\rm n\mid a(x-c)\iff \color{#0A0}{\bar n\mid \bar a}\, (x-c)\iff \bar n\mid x-c\ \ \ by\ \ \color{#0A0}{ Euclid's\ \ Lemma}$
This solution $\rm\:x \equiv c\pmod{\bar n}\:$ splits into precisely $\rm\:\color{#C00}d\:$ classes mod $\rm\: \color{#C00}d\bar n = n,\:$ namely
$\rm x\equiv c\,\ (mod\ \bar n)\iff x\,\equiv\, c,\,\ c\! + \bar n,\,\ c\! + 2\bar n,\,\ c\! + 3\bar n,\, \ldots,\, c\! + (\color{#C00}{d}\!-\!1)\bar n\ \ (mod\ {\color{#C00}d\bar n})$
since, by the $\rm\color{blue}{Division}$ Algorithm, $\rm\: c + \color{blue}{j}\,\bar n\, =\, c + (\color{blue}{r\! +\! qd})\,\bar n \,\equiv\, c + r\,\bar n\, \ (mod\ \color{#C00}d\bar n)\ $ for $\rm\: r\in [0,\color{#C00}{d}\!-\!1],\ $ and this interval contains precisely $\rm\:\color{#C00}d\:$ integers, namely $\rm\:0,1,2,\, \ldots,\, \color{#C00}{d}\!-\!1.$