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?


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

  • $\begingroup$ Hard to follow your question. Sorry. What do you mean to get an answer 77? $\endgroup$ – Juniven Mar 5 '17 at 11:17
  • $\begingroup$ What are you solving for? $\endgroup$ – Richard Ambler Mar 5 '17 at 11:17
  • $\begingroup$ It's the last steps of euclidean algorithm to find 5 inverse (mod 96). $\endgroup$ – user963241 Mar 5 '17 at 11:20
  • $\begingroup$ "$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}$. $\endgroup$ – hmakholm left over Monica Mar 5 '17 at 11:27
  • $\begingroup$ @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. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – user963241 Mar 5 '17 at 21:24
  • $\begingroup$ @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). $\endgroup$ – 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}.$$

| cite | improve this answer | |

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.