What is wrong with my solution to this equation : $346 x+ 1250 \equiv 49 \pmod{105}$?

Question

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$

Answer 1

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}.$$

Answer 2

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}$$

Answer 3

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.$$

Answer 4

The very first thing I would do is reduce the coefficients (mod 105)! 346= 3(105)+ 31 so 346= 31 (mod 105) and 1250= 11(105)+ 95 so 1250= 95 (mod 105). The equation is equivalent to 31x+ 95= 49 (mod 105). Then subtract 95 from both sides: 49- 95= 49+ 105- 95= 59 so 31x= 59 (mod 105).

That is the same as saying that 31x= 59+ 105y for some integers x and y. 31x- 105y= 59 is a "linear Diophantine equation" and there is a simple way of solving such equations- the "Euclidean Algorithm". First look at the equation 31x- 105y= 1. 31 divides into 105 three times with remainder 12: 105- 3(31)= 12. 12 divides into 31 twice with remainder 7: 31- 2(12)= 7. 7 divides 12 once with remainder 5: 12- 7= 5. 5 divides into 7 once with remainder 2: 7- 5= 2. Finally, 2 divides into 5 twice with remainder 1: 5- 2(2)= 1. Replace that "2" with 7- 5: 5- 2(7- 5)= 3(5)- 2(7)= 1. Replace that "5" with 12- 7: 3(12- 7)-2(7)= 3(12)- 5(7)= 1. Replace that "7" with 31- 2(12): 3(12)- 5(31- 2(12))= 13(12)- 5(31)= 1. Replace that "12" with 105- 3(31): 13(105- 3(31))- 5(31)= 13(105)- 44(31)= 1. So one solution to 31x- 105y= 1 is x= -44, y= -13. But it is easy to see that x= -44+ 105k, y= -13+ 31k is also a solution: 31x- 105y= 31(-44+ 105k)- 105(-13+ 31k)= -1364+ (31)(105)k+ 1365-(105)(31)k= 1.

We want a positive solution so take k= 1: x= -44+ 105= 61. 31x= 1 (mod 105) is satisfied by x= 61: 31(61)= 1891= 18(105)+ 1. Finally, to solve 31x= 59 (mod 105), multiply by 59: x= 61(59)= 3599= 34(105)+ 29. x= 29 satisfies 31x= 59 (mod 105).

Checking in the original problem: 346(29)+ 1250= 11284= 107(105)+ 49= 49 (mod 105)