Originally Posted by

**johnsomeone** Back in AlgebraI, you learned that you solve 4x = 28 by "dividing both sides by 4". You later learned that that's the same as multiplying both sides by 1/4. A little later in that course, you learned that you can solve (3/2)y = 15 by multiplying both sides by 2/3. What was happening there is that you were exploiting that (4)(1/2) = 1 (and (3/2)(2/3) = 1), and that (1)(x) = x (and (1)y = y):

4x = 28, so (1/4)(4x) = (1/4)(28), so (1/4)(4)(x) = 28/4, so (1)(x) = 7, so x = 7.

(3/2)y = 15, so (2/3)(3/2)y = (2/3)(15), so (1)y = 30/3, so y = 10.

So "dividing" is "multiplying by the multiplicative inverse", where the "multiplicative inverse" is the thing you multiply a number by to get a result of 1.

The same idea is what's happening "modulo 7" (or modulo "anything"): The "multiplicative inverse" (usually just called the inverse) of "3 modulo 7" is "the number modulo 7" that when multiplied by "3 modulo 7" gives a result of "1 modulo 7".

"(-2)(3) modulo 7" is "-6 modulo 7" is "(-6+7) modulo 7" is "1 modulo 7", so "-2 is an inverse of 3 modulo 7".

Note that 5 is also an inverse of 3 modulo 7:

"(5)(3) modulo 7" is "15 modulo 7" is "(15-14) modulo 7" is "1 modulo 7", so "5 is an inverse of 3 modulo 7".

Anything congruent to -2 modulo 7 will be an inverse of 3 modulo 7.

That's how we solve things like: 3x = 4 mod 7.

3x = 4 mod 7, so (-2)(3x) = (-2)(4) mod 7, so (-6)x = -8 mod 7, so (1)x = (-8+14) mod 7, so x = 6 mod 7.

It's basically the same as AlgebraI, except now everything is "modulo 7". (There are some differences, obviously, but the point is that we solve "3x = 4 mod 7" the same kinda way we'd solve "3x = 4", namely, we "divide both sides by 3", excpet modulo 7 that means multiplying by an inverse of 3 modulo7, which was here -2 modulo 7.

To find the inverse of "a mod n" the __first thing to check__ is that the gcd(a, n) = 1.

For small numbers, then usually enumeration/clever guessing is usually the easiest way.

The inverse of 4 mod 7 = ?

First note that gcd(4, 7) = 1.

Look at multiples of 7, add 1, and scan that list for divisibility by 4:

Multiples of 7: 0, 7, 14, 21

Multiples of 7, then +1 (numbers = 1 mod 7): 1, 8, 15, 22

8 is divisible by 4. (4)(2) = 8 = 1 modulo 7, so an inverse of 4 modulo 7 is 2 modulo 7.

The inverse of 5 mod 21 = ? Mulitply 5 by something so that the result leaves remainder 1 when divided by 21:

Note gcd(5, 21) = 1.

Look through the multiples of 21: 0, 21, 42, 63, 84

Look through the numbers leaving a remainder of 1 when divided by 21: 1, 22, 43, 64, 85.

Thus 5 times 17 = 85 leaves a remainder of 1 when divided by 21. (5)(17) = 1 mod 21. Thus 17 is the inverse of 5 modulo 21.

The "algorithmic way" is, once gcd(a, n) = 1, to apply "Euclid's Algorithm For The GCD" to find intgers x and y such that:

xa + yn = 1.

Then (x)(a) = 1 modulo n, so "a inverse modulo n is x modulo n"

However, this is only useful if writing a computer program. Enumeration/clever guessing is much easier until the numbers become large (say, maybe 3 digits or more - though finding the inverse of 37 mod 83 is probably unpleasant.)