Find all $x \in \mathbb{Z}_{501}$ for which $51x \equiv 36$ I am stuck with one problem from my discrete math class and don't know how to solve it. I will be grateful for any help!
Find all $x \in \mathbb{Z}_{501}$ for which $51x \equiv 36$, where the multiplication is in $\mathbb{Z}_{501}$.
I started solving it like this:
\begin{align}
51x & \equiv 36 \pmod{501}\\  
51x & \equiv 36 + k501\\  
51x + 501y & = 36  
\end{align}
After this, I found $\gcd(51,501)$, which is $3$:
\begin{align}
501 & = 9 \cdot 51 + 42\\  
51 & = 1 \cdot 42 + 9\\  
42 & = 4 \cdot 9 + 6\\  
9 & = 1 \cdot 6 + 3\\  
6 & = 2 \cdot 3 + 0
\end{align}  
After this, using back-substitution:
\begin{align}
3 & = -6 \cdot 501 + 59 \cdot 51\\  
36 & = 708 \cdot 51 - 72 \cdot 501
\end{align}  
Then I divided equation by the $\gcd$ and solved $17x+167y = 0$.  
So my final answers are $x = 708 + 167k$ and $y= -72-17k$ (In our case we don't need $y$, though.)  
Answers from my book are $x_1 = 40$, $x_2 = 207$ and $x_3 = 374$, and I don't know how can I get them.  
 A: What you have done thus far is correct.  Observe that 
$$708 \equiv 40 \pmod{167}$$
since 
$$708 = 4 \cdot 167 + 40$$
The distinct solutions are all the integers in $\{0, 1, 2, 3, \ldots, 500\}$, the set of residues modulo $501$, that satisfy the congruence $x \equiv 40 \pmod{167}$.  They are 
\begin{align*}
x_1 & \equiv 40 + 0 \cdot 167 \equiv 40 \pmod{501}\\
x_2 & \equiv 40 + 1 \cdot 167 \equiv 207 \pmod{501}\\
x_3 & \equiv 40 + 2 \cdot 167 \equiv 374 \pmod{501}
\end{align*}
A: Note $\,708\bmod{\!167} = 40\ $ thus $\,708+167k = 40+167n.\ $ Next, to lift this solution from modulus $167$ to $\,\color{#c00}3\cdot 167 = 501$ we divide $n$ by $\color{#c00}3,\,$ so $\, n = i + \color{#c00}3j,\,$ which yields
$$\begin{align}{\rm mod}\,\ \color{#c00}3\!\cdot\! 167\!:\,\ 40 + 167n &\equiv 40+167(i+\color{#c00}3j), \  {\rm for} \  \,0\le i < 3\\
&\equiv 40+167\,i,\quad {\rm for}\ \ \ i=0,\,1\,,2\\
&\equiv 40,\ 40\!+\!167\!\cdot\! 1,\ 40\!+167\!\cdot\!2\\
&\equiv 40,\ 207,\ 374
\end{align}$$
A: There is an algorithm for this kind of equation.
I usually reformulate:
$$
51 x \equiv 36 \pmod{501} \iff \\
(51 x) \bmod 501 = 36 \iff \\
51 x = 501 q + 36 \iff \\
51 x - 501 q = 36 \quad (*)
$$
where $x\in \mathbb{Z}_{501}$ and $q \in \mathbb{Z}$. 
The last equation $(*)$ can be interpreted as a linear Diophantine equation, where we limit the solutions for $x$ from $\mathbb{Z}$ to $\mathbb{Z}_{501}$.
Number of solutions:
If $g = \gcd(51, 501)$ divides $36$, we have infinite many solutions $(x,q) \in \mathbb{Z}^2$, otherwise none. We have $g=3 \mid 36$, so we got the first case.
Solution of the homogeneous equation:
The reduced equation (divided by $g$) is
$$
17 x - 167 q = 12
$$
The homogeneous equation is
$$
17 x - 167 q = 0 \quad (**) \iff \\
17 x = 167 q
$$
$\gcd(17,167)=1$ implies $17\mid q$ and $167\mid x$. So the homogeneous equation $(**)$ is solved by
$$
\{ (167 t, 17 t) \mid t \in \mathbb{Z} \}
$$
Finding a particular solution:
The extended Euclidean algorithm for $(51,-501)$ gives numbers $s=59, t=6$ (and $g=3$) such that
$$
51 s - 501 t = g = 3 \iff \\
51 (12\cdot 59) - 501 (12\cdot 6) = 12\cdot 3 = 36
$$
so a particular solution of $(*)$ is $(x_p, q_p) = (708, 72)$.
The total solutions are
$$
\{ (708 + 167 t, 72 + 51 t) \mid t \in \mathbb{Z} \}
$$
Limiting to $\mathbb{Z}_{501}$:
We have 
$$
708 + 167 t \ge 0 \iff
t \ge -708/167 = -4.23\dotsb
$$
and
$$
708 + 167 t \le 500 \iff
t \le -208/167 = -1.24\dotsb
$$
so $t\in \{ -2,-3,-4\}$ and $x \in \{ 40, 207, 374 \}$.
