# How do you find all the solutions in $\Bbb Z^+$

\begin{align*} 5x & \equiv 1 \pmod{1303} \\ 5x & \equiv 10 \pmod{30} \end{align*} Can you post a step by step solution? I am reviewing for my finals.

-
I would have thought there would be lots of tutorials on simultaneous linear congruences already.... – Simon Hayward Nov 29 '12 at 20:40
– Simon Hayward Nov 29 '12 at 20:41

$$5x \equiv 10 \pmod{30} \implies x \equiv 2 \pmod6$$ $$5x \equiv 1 \pmod{1303} \implies 5x = 1303k + 3910 \implies x = 1303 \ell + 782$$ Since $6 \vert x -2$, we have that $6 \vert 1303 \ell \implies 6 \vert l$. Hence, $$x = 7818 M + 782$$

-

More generally, replace $1303$ by any integer $\rm\:c = \color{#C00}{13} + 30\,n.\:$ Then

$\$ Easy CRT $\rm\,\Rightarrow\, 5x \equiv 1\! +\! c\,\left[\dfrac{9}{c} mod\ 30\right]\! \equiv 1\! +\! c\,\left[\dfrac{39}{\color{#C00}{13}} mod\ 30\right]\! \equiv 1\!+\!3c\pmod{ 30c}$

So we infer that $\rm\ x \equiv \dfrac{1+3c}5\equiv \dfrac{40+90n}{5}\,\equiv\, 9+18n\pmod{6c}$

So $\rm\,c\! =\! 1303\:\Rightarrow\:x \equiv \dfrac{1+3\!\cdot\!1303}{5}\equiv\dfrac{3910}5\equiv 782 \pmod{6\cdot 1303}$

-