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
Asked
Active
Viewed 222 times
2 Answers
0
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}$$
tong_nor
- 3,994
-
Where did you get 2? Is it because $17 \cdot 2 \pmod{35} = 1$? – John Mar 03 '16 at 19:24
-
$17\cdot 2\equiv -1\pmod{35}$, but yes - it is nice to obtain $\pm 1$ somewhere – tong_nor Mar 03 '16 at 19:25
-
So this process is fairly similar, if not identical to finding the multiplicative inverse. Are they essentially the same concept, just applied to different situations? – John Mar 03 '16 at 19:29
-
A multiplicative inverse is one number (if exists). A linear congruence if has one solution then it has infinitely many solutions. Here a multiplicative inverse would be $21$. A solution of congruence is $x\equiv 21\pmod{35}$ - this is an arithmetic sequence $21+35k$, $k\in\mathbb{Z}$. – tong_nor Mar 03 '16 at 19:41
0
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
