[Math] How to solve for mod to get a value

modular arithmetic

I want to solve the following part involving mod:

1 = -5(19) (mod 96)

Apparently, this mod in brackets (mod 96) here is different from the mod that I know e.g. its not the remainder value that you get by dividing.

What of kind of mod is it and how can I solve it step by step to get the result which is 77?

Update:

Okay, so I am trying to find what's 5 inverse mod 96.

By following euclidean algorithm approach here's what I am doing:

Step1: Find GCD of 5 and 96

96 = 5(19) + 1

which becomes 1 = 96-5(19) when expresses in 1 term

Step 2: Take mod (96) both sides

So I will have left:

1 = -5(19) (mod 96)

That's from where I need to solve it to get 5 inverse (mod 96).

Best Answer

The notation $$ a\equiv b \pmod n $$ means that $a$ and $b$ are in the same residue class modulo $n$. If you're more used to $\bmod$ as a binary operator, this is the same as saying $$ a\bmod n = b\bmod n$$ though we have to remember that the $\bmod$ here is one that always produces a result in $[0,n)$ even for a negative argument, such that, as will be relevant here, $(-19)\bmod 96 = 77$.

When you're being asked to find a multiplicative inverse of $5$ modulo $96$, what this means is to find an $x$ such that $$\tag1 5x\equiv 1 \pmod{96} $$ Through the previous steps of the solution you have reached the knowledge that $$\tag2 1 \equiv -5 \cdot 19 \pmod{96} $$ which is almost the same as what you're looking for, except that

  1. The $1$ is on the other side -- but that doesn't matter, because the definition of $\equiv$ is clearly symmetric in $a$ and $b$.
  2. There is a $-5$ instead of a $5$ in $\text{(2)}$. But we can get a $5$ instead by rembering (basic aritmetic) that $(-5)\cdot 19 = 5\cdot(-19)$.

So, since we know $\text{(2)}$ is true, we also know $$\tag3 5\cdot(-19) \equiv 1 \pmod{96} $$ which tells us that $-19$ is a solution for $x$ in $\text{(1)}$.

All that is left to do is find the canonical representive of the residue class that contains $-19$, by adding or subtracting some multiple of $96$ to get it into the range $[0,96)$: $$ -19 \bmod 96 = 77 $$ In other words, since changing one factor by a multiple of $n$ doesn't change the residue modulo $n$, we also know that $$ 5\cdot 77 \equiv 1 \pmod{96}$$ which says that $5$ and $77$ are multiplicative inverses modulo $96$.

Related Question