Finding the inverse of a congruence

Question

I am studying Chinese Remainder Theorem in my Information Theory class. It involves solving congruences. All I know about congruences is what I learned from watching YouTube videos. I can do some congruences; the straightforward ones. However, I get stuck in the nutty ones.

Here is the one where I got stuck:
$$ 88 y_2 \equiv 1 (mod 9) $$

I could solve it a couple of steps and got stuck at:
$$ 7 y_2 \equiv 10 (mod 9) $$

It was only because the instructor in the video solved this that I could arrive at an answer. He subtracted 9 from the left side of the congruence.

I know this process is called "finding the inverse of a congruence" but I am no good at it. Can someone please tell me how it is done ?

Answer 1

The notation $\pmod{n}$ means that once you count till $n - 1$, you re-start counting from $0$. It is also known as clock arithmetic. Therefore, $n \equiv 0 \pmod{n}, n + 1 \equiv 1 \pmod{n}$ and so on. For example, in your case $10 = 9 + 1 \equiv 1 \pmod{9}$. In general, if we wish to calculate some number $m \pmod{n}$, we need to divide $m$ by $n$ and see what the remainder is. If $m = qn + r$ where $0 \leq r < n$, then $m \equiv r \pmod{n}$.

Answer 2

The first thing to do is to eliminate any numbers smaller than the modulus, which reduces the problem to

$$7y_2\equiv1\pmod9$$

If I understand what you're saying, he subtracted the left side by a multiple of $9$, in this case $9y_2$

$$-2y_2\equiv1\pmod9$$

This is occasionally done in modular arithmetic as working with numbers of smaller magnitude are easier. In this case, if he can add a multiple of $9$ to the right side to obtain a multiple of $2$, he can simply divide both sides. This is simple: add an odd number to an odd number to get an even number.

$$-2y_2\equiv10\pmod9,y_2\equiv-5\equiv4\pmod9$$

$9$ is a small enough modulus that you could do it by trial and error, especially if you narrow down your options by noticing that $$y_2\equiv1\pmod3$$

For larger numbers, there are other methods such as Euler's Theorem or the extended Euclidean algorithm. For example, let's say I wanted the inverse of $7$ modulo $31$. Since $31$ is prime, the inverse of $7$ modulo $31$ is equivalent to $7^{30}$, which is slightly less daunting to calculate then it looks.

$$7^2\equiv49\equiv18\equiv-13\pmod{31}$$ $$7^4\equiv-13\times-13\equiv169\equiv14\pmod{31}$$ $$7^8\equiv14\times14\equiv196\equiv10\pmod{31}$$ $$7^{16}\equiv10\times10\equiv100\equiv7\pmod{31}$$

Normally, I'd multiply all the above values together to get $7^{30}$, but it looks like $7^{16}\equiv7\pmod{31}$ meaning that $7^{15}\equiv1\pmod{31}$, so $7^{14}$ will be our inverse.

$$7^{14}=7^8\times7^4\times7^2\equiv10\times14\times-13\equiv140\times-13\equiv16\times-13\equiv-15\times-13\pmod{31}$$

$-15$ is easier to work with here thanks to an algebra trick.

$$15(13)=(14+1)(14-1)=14^2-1=195\equiv9\pmod{31}$$

And sure enough

$$7\times9=63\equiv1\pmod{31}$$