Method to Solve Linear Congruences

Question

Can someone walk through how to solve $17x \equiv 7 \pmod{35}$? I'm having a lot of trouble with this and finding multiplicative inverses.

I tried $\mathbf35 = 5(7) + 0$, but I'm not sure what to do since the remainder is 0

Answer 1

Observe that (since 2 and 35 relatively prime) $$35\mid (17x-7)\iff 35\mid2(17x-7)\iff 35\mid 34x-14\iff 35\mid -x-14\iff x\equiv -14\equiv 21\pmod{35}$$

Answer 2

First of all, notice that 17 and 35 are coprime. If they weren't, you would have to take that into account, but anyway:

You are allowed to add any multiple of 35 to one side of the equation as $35\equiv 0 \pmod {35}$.

Therefore, you can keep adding 35 to the right hand side until it is a number divisible by 17.

$17x\equiv 7+35n \pmod {35}$

Once you've found an $n$ that works, you are allowed to divide both sides of the congruence by 17 (as long as 17 and 35 are coprime).

For congruences where the number you are trying to divide through and the modulo base are not coprime, you will also have to change the modulo base you are considering by dividing through by the gcd (greatest common divisor) of the 2 numbers.

This answer should help you out: Dividing the linear congruence equations