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?
 A: 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..
A: 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.
A: $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$
A: 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.
A: 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 $
