1

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

user963241
  • 649

3 Answers3

2

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

hmakholm left over Monica
  • 286,031
  • I haven't done a division with negatives like this before. So, is this how: http://i66.tinypic.com/20ptz5v.gif I will divide the -19 and 96 to get mod 77? – user963241 Mar 05 '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 05 '17 at 21:30
0

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

Juniven Acapulco
  • 9,654
0

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

Student
  • 4,438
unseen_rider
  • 778