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

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?

• 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. – usukidoll May 8 '14 at 22:32
• @usukidoll For finding the linear combination $ax + by = \gcd(a,b)$ perhaps this post will be useful. – Anant May 14 '14 at 18:43

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

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.

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

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.

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

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$