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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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 $

Answer 5

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