1
$\begingroup$

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$

$\endgroup$
  • 2
    $\begingroup$ You have to multiply by $61$ the quantity $49-1250$. $\endgroup$ – aleio1 Feb 2 '18 at 13:23
  • $\begingroup$ Also try to solve it by CRT. $\endgroup$ – aleio1 Feb 2 '18 at 13:25
  • $\begingroup$ Please remember that you can choose an aswer among the given is the OP is solved, more details here meta.stackexchange.com/questions/5234/… $\endgroup$ – gimusi Mar 9 '18 at 22:27
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I preferred your previous edit to be honest, but I have run out of votes to give anyway.….Much better :) $\endgroup$ – Feeds Feb 2 '18 at 13:32
  • $\begingroup$ @user477343 I decided to edit this way to emphasize that the problem with OP's computation was really about the order in which the operations were performed. I thought the simplification of the factors was a bit distracting from that point of view. $\endgroup$ – Arnaud D. Feb 2 '18 at 13:38
  • $\begingroup$ I just like answers that don’t skip too many steps. I think it is much more clearer and requires less thinking for those people who read through answers and like to double-check whether or not they are indeed correct (like me). $\endgroup$ – Feeds Feb 2 '18 at 14:03
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.