What are ways to solve Linear Congruences? I am aware of something called the Chinese Remainder Theorem, using modulo inverses.
For example,
$$3x \equiv 17 \pmod{2014}$$
Instead of finding inverse modulo, How can I use the Chinese Remainder Theorem?
Or any other methods?
 A: Using $\ 2014 = 2\cdot 19\cdot 53\ $ we apply CRT.
$ {\rm mod}\ 19\!:\ x \equiv \dfrac{17}{3}\equiv \dfrac{17+19}{3}\equiv\ \color{#0a0}{12}$
$ {\rm mod}\ 53\!:\ x \equiv \dfrac{17}{3}\equiv \dfrac{17-53}{3}\equiv \color{#c00}{-12}$
$ {\rm mod}\ 19\!:\ \color{#0a0}{12}\equiv x\equiv \color{#c00}{-12}+53n\equiv -12-4n\iff4n\equiv -24\iff n\equiv -6$
Thus $\,{\rm mod}\ 19\cdot 58\!:\ x\equiv -12+53(-6)\equiv -330\equiv 677$
Finally $\,{\rm mod}\ 2\!:\ 3x\equiv 17\iff x\equiv 1,\,$ hence $\ x\equiv 677\pmod{2\cdot 19\cdot 58}$
Beware $ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.
Remark $\ $ Generally it is much easier not to use CRT to invert small numbers, e.g. we can universally invert $3$ mod $\,n\,$ as follows. ${\rm mod}\ 3\!:\ n\not\equiv 0\,\Rightarrow\,n\equiv \pm 1,\,$ so $\, \color{brown}{3\mid 1\pm n}\,$ hence
$${\rm mod}\ n\!:\,\ \dfrac{1}{3}\equiv \color{brown}{\dfrac{1\pm n}{3}} = k\in\Bbb Z$$
This corresponds to using a single step of the extended Euclidean algorithm (using remainders of least magnitude, i.e. using $\{-1,0,1\}$ as reps mod $\,3.)$
A: We don't even need CRT
As $17\equiv-1\pmod3,2014\equiv1;17+2014\equiv0$ and $(2014+17)/3=677$
$3x\equiv17\pmod{2014}\equiv17+2014$
$\iff3(x-677)\equiv0\pmod{2014}$
As $3\nmid2014,(3,2014)=1\implies x-677\equiv0\pmod{2014}$
See $\#12$th property of Congruence
A: I know this solution doesn't use CRT (there has already been given a solution that uses this) but I thought i'd give the easiest way to solve it.
Since $2013 = 3\times 671$ multiplying both sides of the congruence by $671$ gives:
$2013x \equiv 671(17) \bmod 2014$
Then:
$-x \equiv 671(17) \bmod 2014$
Hence:
$x \equiv -671(17) = ... \equiv 677 \bmod 2014$.
