# How can I solve for mod to get a value?

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

• Hard to follow your question. Sorry. What do you mean to get an answer 77? – Juniven Mar 5 '17 at 11:17
• What are you solving for? – Richard Ambler Mar 5 '17 at 11:17
• It's the last steps of euclidean algorithm to find 5 inverse (mod 96). – user963241 Mar 5 '17 at 11:20
• "$1\equiv -5\cdot19\pmod{96}$" is not something it makes sense to solve, or something that gives a result. It is just a true statement of fact: the numbers $1$ and $-5\times 19$ (which is $-95$) differ by a multiple of $96$. If you have found it in a context where someone continues "... therefore the result is 77", then you haven't quoted enough of the context to let us see what that someone is actually doing -- the number $77$ has nothing in particular to do with the fact that $1\equiv -5\cdot19\pmod{96}$. – hmakholm left over Monica Mar 5 '17 at 11:27
• @Henning Makholm Sorry. So I rather delete my answer. But honestly I based my answer to his comment which says he want to find the multiplicative of $5$ in mod 96. – Juniven Mar 5 '17 at 11:32

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

• I haven't done a division with negatives like this before. So, is this how: i66.tinypic.com/20ptz5v.gif I will divide the -19 and 96 to get mod 77? – user963241 Mar 5 '17 at 21:24
• @user963241: An ordinary rational division without remainder gives $(-19)\div 96 = -0\frac{19}{96}$. To find the modulus, round the quotient down (towards minus infinity) to $-1$, multiply by $96$ and subtract this from $-19$: $$-19 - (-1 \cdot 96) = 77$$ This procedure works uniformly both for positive and negative dividends. (Only the shortcut of reading the remainder directly off from the long division doesn't). – hmakholm left over Monica Mar 5 '17 at 21:30

Based on the update of your post, you are looking for $x$ for which $$5x\equiv 1\pmod{96}.$$ This $x$ is called the multiplicative inverse of $5$ in mod $96$. Now, we have $$1\equiv (-19)5\pmod{96}$$ which means that $$5(-19)\equiv 1\pmod{96}.$$ This means any $x$ such that $$x\equiv -19\pmod{96}$$ is the inverse of $5$ in mod $96$. Observe that $$-19\equiv 77\pmod{96}.$$ Hence, all solutions of $x$ are given by$$x\equiv 77\pmod{96}.$$

$1 \equiv -5(19) \mod 96$ is equivalent to $1 \equiv -95 \mod 96$ by multiplying out the brackets.

For your question it's equivalent to going round a clock with $96$ hours on it - each time you reach $96$th hour it goes back to $0$ and starts again.

This can also be extended to negative numbers, and adding multiples of $96$. Hence:

$$1 \equiv -5(19) \mod 96 \equiv 1 \mod 96$$