Having trouble understanding the concept of multiplicative inverse of modulo

Question

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.

Answer 1

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

Answer 2

For the equation that you have given, $27$ does have a multiplicative inverse modulo $4$ since $$27\times3\equiv 1\pmod 4$$ so you can solve the equation in the 'normal' way:- $$x\equiv 10\times3\equiv 2\pmod 4.$$

Answer 3

Since $37\ne 0\pmod 4,$ divide both sides by $37$ to get $$x=\frac{10}{37}\pmod 4=\frac{10+4n}{37}.$$ You need now only find integer values of $n$ that make $x$ an integer. Clearly, for positive $n,$ we must have $n>6.$

An easier way is to reduce both sides modulo $4$ and search for solutions in $\{0,1,2,3\}.$ Then the equation becomes $x=2,$ whence all solutions have the form $2+4n$ for integer $n.$

Answer 4

You have to remember you are not solving for integers but for classes of integers.

There a four classes of integers.

There is $ZERO = \{.....,-12,-8,-4,0,4,8,12,.....\}$. This is the class of all integers that are divisible by $4$.

There is $ONE = \{.....,-11,-7,-3,1,5,9,13,......\}$. This is the class of all integer that have $1$ as a remainder when you divide by $4$.

There is $TWO = \{.....,-14,-10,-6,-2,2,6,10,14,18,22,26,30,34,38,42,46,50,54=2*27, 58,....\}$. This is the class of all integers that have $2$ as a remainder.

And the last class if $THREE = \{.....,-9,-5,-1, 3, 7,11,.....\}$.

Every integer is one and only one of these classes. If two integers $a,b$ are in the same class we say they are equivalent or congruent and we write $a \equiv b \pmod 4$. This will mean four things i) $a = b + 4k$ for some multiple $4k$ of $4$; ii) that $a-b=4k$ so $a-b$ is a multiple of $4$ or in other words $4|a-b$. iii) $a$ and $b$ have the same remainder when divided by $4$ and iv) $a$ and $b$ are both in the same one of the four classes.

And they are for all our purposes considered to be the same.

So in solving $27x \equiv 10\pmod 4$ we want to know what class $x$ belongs to given that $27x$ and $10$ are in the same class.

You figured out $1 = 4*7 + (-1)*27$. This means $1$ and $(-1)*27$ are both in the same class; $1\equiv (-1)*27 \pmod 4$ and, indeed, both are in $ONE = \{....., -31, -27, -23, -19,-15,-11,-7,-3, 1, 4, ....\}$. So $1\equiv (-1)*27$.

You then multiplied both sides by $10$ and got $10 = 4*70 + (-10)*27$. This the hard way to do it but it isn't wrong. $10$ and $-270$ are both in the same class and $10\equiv -270\pmod 4$. They are both in $TWO = \{........, -270= 4*(-68)+2, -266,-262, ........, -2,2, 6,10, 14,.....\}$.

So the $x$s that will put $10$ and $27x$ will all be in the same class that $-10$ is. And that class is .... $TWO = \{......,-10,-6, -2,2,6,10,.....\}$.

....... that's the hard way to do it....

The easy way is:

$27x \equiv 10\pmod 4$. Now we can replace $27$ with anything in the same class as it. As $27 = 4*6 + 3$ we know that $27$ is in $THREE$. And $3$ is in THREE. SO we can replace $27$ with $3$ and the whole thing will still be true.

SO $3x\equiv 10 \pmod 4$. And we know $10 = 2*4 + 2$ so $10\in TWO$ and $2\in TWO$ so we can replace $10$ with $2$ and everything will still be true.

$3x \equiv 2\pmod 4$.

Now we know that because $\gcd (3,4) = 1$ that there is an integer, we will call it $INV(3)$. so that $INV(3)\times 3 \equiv 1 \pmod 4$. What class is $INV(3)$ in?

Well, a bit of experimenting and we notice that $3\times 3=9 = 2*4 + 1\equiv 1 \pmod 4$. So $INV(3)$ can be any number that is in the same class that $3$ is in.

So we can multiply both sides by $3$ and get:

$3*3x \equiv 2*3 \pmod 4$

$9x \equiv 6 \pmod 4$ and we can replace $9$ with $1$ and get

$x \equiv 6\pmod 4$.

So $x$ is in the same class that $6$ is in. That is $TWO$.

That is the same clase that $2$ is in, and that $10$ is in or that $-10$ is s in or that $(-2)*27$ is.

So $x \equiv 6\pmod 4 \equiv 2\pmod 4\equiv 10\pmod 4 \equiv -10\pmod 4 \equiv -54\pmod 4$ and any one of those can be used to express a solution.

$2$ is the prefered solution because it is convenient to choose values between $0$ and $3$. But all of them are equally correct. $x$ can be any number in $TWO$.

.... and now, ... I can tell you that no-one actually calls these classes $ZERO, ONE, TWO THREE$. We just refer to them by any integer that is in the clases.

So $x \equiv 2 \pmod 4$ is considered a solution.