I'm trying to solve equations like this
$$27x \equiv 10 \pmod 4$$
I understand that in a regular equation you have to multiply by the inverses of each number to isolate the variable. For example:
$$27x = 10 \Leftrightarrow x = 10/27$$
You can't do that with modulo so the method that is used is to find if the gcd = 1, if it does it can be solved and you work your way back and write 1 as a linear conbination of 27 and 4 in this case, skipping a lot of steps you get
$$1 = 7*4 + (−1)*27$$
Then you multiply both sides by 10
$$10 = 70*4 + (−10)*27$$
And this can be rewritten as
$$10 + 70*4 = -10*27 \Leftrightarrow \\
-10*27 \equiv 10 \pmod 4$$
I don't understand why the answer is $x=2$ and not $x=-10$. -10 is 2 mod 4. Yet both -10*27 and 2*27 are 2 mod 4, not 10. I don't understand. The idea of a multiplicative inverse still puzzles me.
Best Answer
$-10$ is $2\pmod4$. So either answer will do. $27\cdot 2\cong27\cdot-10\cong10\pmod4$.
Also, $2\cong10\pmod 4$. So it all works out.
As you noted, $x$ has an inverse $\pmod n$ precisely when $(x,n)=1$.
So you have $-1\cdot27+7\cdot 4=1$. Thus $27^{-1}\cong-1\pmod4$.
So we can "solve" $27x\cong10\pmod 4$ by multiplying both sides by $27^{-1}$ or $-1$ thus: $x=-1\cdot 10\cong-10\cong2\pmod 4$.