<s>[INST] What is wrong with my solution to this equation : $346 x+ 1250 \equiv 49 \pmod{105}$? I'm not sure how to get $x$ but with my way $x = 39$. The solution for $x$ is 29 though. Could anyone possibly help me with the calculating method?
Mine:
$\gcd(346,105) = 1 \Rightarrow  x = a^{-1} \cdot b \pmod m \Rightarrow  346^{-1} \pmod{105} = 61 \Rightarrow  (61\cdot49)+1250 \pmod{105} = 39$
 [/INST] Note that
$$346x+ 1250 \equiv 49 \pmod {105} \iff 31x \equiv 59 \pmod {105}$$
thus since $gdc(31,105)=1$ we can find the inverse of $31 \pmod {105}$ by Euclidean's algorithm.
As an alternative by CRT we get
$$\begin{cases}31x \equiv 59 \pmod {3}\iff x \equiv 2 \pmod {3} \\31x \equiv 59 \pmod {5} \iff x \equiv 4 \pmod {5} \\31x \equiv 59 \pmod {7} \iff 3x \equiv 3 \pmod {7} \iff x \equiv 1 \pmod {7}  \end{cases}$$
thus


*

*$ x \equiv 1 \pmod {7} \implies x=1+7k$

*$x=1+7k \equiv 4 \pmod {5}\implies 1+2k \equiv 4\pmod 5 \implies 2k
   \equiv 3\pmod 5 \\\implies k \equiv 4\pmod 5 \implies x=1+7(4+5h)=29+35h$

*$x=29+35h \equiv 2 \pmod {3} \implies h\equiv 0 \pmod 3$


thus $$x=29 \pmod {105}$$
</s>