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$
 A: The problem is with the way you isolate $x$ in the equation, especially the $1250$ term. Starting from
$$346x+1250 \equiv 49\pmod{105},$$
you need first to substract $1250$ on both sides, and only then to multiply both sides by $61$ (the inverse of $346$ modulo $105$). This gives you
$$x\equiv (49-1250)\cdot 61\equiv 59\cdot 61\equiv 3599\equiv 29 \pmod{105}.$$
As an aside, you would also probably make your life a bit easier by simply reducing the numbers a little bit. $346\equiv 31\pmod{105}$ and $1250\equiv 95\pmod {105}$, so the equation is equivalent to
$$31x+95 \equiv 49\pmod{105}.$$
A: 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}$$
A: Note that $346\equiv 31$ and  $1250\equiv -10\mod 105$, so the congruence really is
$$ 31x\equiv 49+10\mod 105. $$
Now the  extended Euclidean algorithm yields $31^{-1}\equiv 61\mod 105$, so the solution is
$$x\equiv 61\cdot 59=60^2-1\equiv 29\mod 105.$$
