3
$\begingroup$

I'm not exactly sure how to solve these modular problems involving a variable. Can someone solve this (trivial) example with explanation?

I found the answer (4) by trial and error, however, I'm sure this isn't the most efficient approach.

Help?

$\endgroup$
  • $\begingroup$ I had a similar problem like this too that I submitted during yesterday's lecture which was solve $23x = 1 (mod 39)$. My professor wrote the equation down as $23x+39y=1$ and used $gcd (23,39) $ which is easy with Euclid's Algorithm. However, finding the linear combination is really confusing. I understand that I have to substitute, but then two strange numbers pop up from the second line onward. This is a good question since it also affects me as well. Hopefully someone can explain this with a lot of detail. $\endgroup$ – usukidoll May 8 '14 at 22:32
  • $\begingroup$ @usukidoll For finding the linear combination $ax + by = \gcd(a,b)$ perhaps this post will be useful. $\endgroup$ – Anant May 14 '14 at 18:43
1
$\begingroup$

We have $153=9\cdot 17$, so generally you have to solve both modulo $ 9$ and modulo $17$ then look for a common solution..

Now we are lucky as we can observe that all numbers are divisible by $17$.

Recall that the congruence $85x\equiv 34\pmod{153}$ is equivalent to the divisibility $153\ |\ (85x-34)$, or that to the fraction $\displaystyle\frac{85x-34}{153}$ is an integer. So, we can divide it all by $17$.

We get

$5x\equiv \equiv 2 \pmod9$
$5x\equiv 20 \pmod9\ $ as $2\equiv 20\pmod9$, then divide by $5$:
$x\equiv 4\pmod9$.

So, $13$ and $22$ will be also solutions..

$\endgroup$
1
$\begingroup$

You can use EEA to solve this.

First you have to take $$85x≡34(mod 153)$$ and find the GCD of 85 and 153.

When you apply EEA you will get an answer in the form of $$85x + 153y = GCD(85,153)$$ If the GCD = 1 or GCD(85,153)|34 then you know you have a solution. Otherwise there exists no solution.

After you apply EEA you will get $$85(2) + 153(-1) = 17$$ and you can see that 17|34, so there is a solution. Notice that if you multiply the above equation by a factor of 2, you get $$85(4) + 153(-2) = 34$$ Some re-arranging gives you the definition of modulus and you can conclude that $$x_0= 4$$ is a solution.

And the set of all solutions is given by $$ x = \{ x_0 + k*(m \div GCD(a, m))\}$$

So all solutions:

$$x = \{ 4 + k*(153/17))\} = \{4 + 9k\} $$ or $$ x \equiv 4 mod(9) $$

This method will always get you a solution or no solutions. Of course, there are shortcuts you can take as you can see in the other answers.

$\endgroup$
1
$\begingroup$

$85x \equiv 34 \pmod {153}$

As 85, 34 and 153 are all divisible by 17, we can write:

$5x \equiv 2 \pmod {9}$

$x = 2/5 \pmod 9 = 4/10 \pmod 9 = 4 \pmod 9$

So, $x = 4 \pmod 9$

$\endgroup$
0
$\begingroup$

You can check $2*85(mod 153)$, which is 17. Multiply by 2 to get 34(mod 153). On problems like this, try to get the remainder near 0. Then you can check if multiplying by a number can get you to your goal.

$\endgroup$
  • $\begingroup$ can you please go into detail? I have a similar problem as the op. like how did you get 17 in this case? $\endgroup$ – usukidoll May 8 '14 at 22:34
  • $\begingroup$ I multiplied 85 by 2, because 153 is pretty close to 85*2, then I found the remainder. $\endgroup$ – Jason Chen May 8 '14 at 22:35
  • $\begingroup$ Using multiplication to get small remainders allows you to multiply again to get larger remainders, as shown above. $\endgroup$ – Jason Chen May 8 '14 at 22:36
  • $\begingroup$ suppose I want to find the linear combination of $85x = 34 (mod 153)$ How would I do that? $\endgroup$ – usukidoll May 8 '14 at 22:43
  • 1
    $\begingroup$ Notice that $153 = 9 \times 17.$ This leaves you to solve a congruence (mod $9$). $\endgroup$ – Geoff Robinson May 8 '14 at 22:53
0
$\begingroup$

As noted, all terms are divisible by 17. This means there will be 17 solutions to the congruence. As noted in the above answers, these will all be $\equiv 4 $ (mod 9). So your solutions will be $x = 4, 13, 22, ... $ In other words $x = 4 + 9k, k= 0, 1, \dots 16 $

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