Inverse of 3 modulo 7

Hi everyone!

I am very confused about how to find an inverse of a modulo m. In this case I need to find the inverse of 3 modulo 7. The book says the following:

"The Euclidean algorithm ends quickly when used to find the greatest common divisor of 3 and 7.

7 = 2 x 3 + 1

From this equation we see that

-2 x 3 + 1 x 7 = 1

This shows that -2 is an inverse of 3 modulo 7. "

I follow what the book is trying to say until it says "This shows that -2 is an inverse of 3 modulo 7." I am not sure how that shows that -2 is an inverse of 3 modulo 7.
Does anyone perhaps have a nice way to find the inverse of a modulo m? :)

Quote:

---

Originally Posted by Nora314

From this equation we see that

-2 x 3 + 1 x 7 = 1

This shows that -2 is an inverse of 3 modulo 7. "

I follow what the book is trying to say until it says "This shows that -2 is an inverse of 3 modulo 7." I am not sure how that shows that -2 is an inverse of 3 modulo 7.

---

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.

Quote:

---

Originally Posted by Nora314

Does anyone perhaps have a nice way to find the inverse of a modulo m? :)

---

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

See Soroban's post below for a more efficient and basically algorithmic approach.

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

Hello, Nora314!

Here is a very primitive solution.

Quote:

---

I need to find the inverse of 3 modulo 7.

---

We have: .

This means: . .for some integer

Solve for

Since is an integer, must be a multiple of 3.

The smallest case occurs when

Hence: .


Therefore, 5 is the inverse of 3, modulo 7.

when we say: "find the inverse of k modulo n", what we mean is:

find an integer m with 1 ≤ m ≤ n-1 such that:

km ≡ 1 (mod n)

which means the same as:

km = 1 + vn, for some integer v (note we don't actually have to find the integer v, it's m we are after).

now if gcd(k,n) = 1, we can always do this. if gcd(k,n) > 1, we cannot.

the euclidean algorithm produces integers r and s such that if gcd(k,n) = 1, we can write 1 = sk + tn. in a moment we'll see exactly how to find these integers, but first, let's see how knowing that they exist helps us find m.

suppose that:

sk + tn = 1

this means:

sk = 1 + (-t)n, or equivalently:

rk ≡ 1 (mod n)

so...can we pick m = s? not quite. s might be < 1, or > n-1. it turns out, however, that there will be a UNIQUE multiple of n, let's call it un for now, such that:

1≤ s + un ≤ n-1.

so...we pick m = s + un, which fits the bill perfectly. note that since:

m = s + un,

m ≡ s (mod n).

ok, as i promised earlier, i'll show how to find s and t, as above. we don't really need t, but we DO need to find s (so we can get m).

we start with two numbers, k and n. we know we can write:

n = qk + r, where 0 ≤ r ≤ k-1. the point here is that r is SMALLER than k (but not negative).

so if a number d divides n, and also divides k:

n = da
k = db

then r = n - qk = da - q(db) = da - d(qb) = d(a - qb), so d divides r as well.

this is true of EVERY number that divides both n and k, and so is true of the greatest of the positive divisors of both: that is, gcd(k,n).

so gcd(k,n) = gcd(k,r) (note we are dealing with smaller numbers now).

now we have two possiibilities: r = 0, or r is not 0. if r = 0, this means k divides n, so gcd(k,n) = k.

but if r is not 0, we repeat the process with k and r:

k = q'r + r', where 0 ≤ r' ≤ r-1.

again, we see that gcd(k,r) = gcd(r,r').

we repeat this process, and keep getting smaller and smaller remainders: r⁽ⁿ⁾ < r^(n-1) <...<r" < r' < r.

eventually, we'll reach a remainder of 0, in which case, the previous remainder is the gcd of k and n.

let's see how this actually works with 3 and 7:

7 = 2*3 + 1

our first remainder is 1.

3 = 3*1 + 0

our 2nd remainder is 0. backing up one step, we see that gcd(3,7) = gcd(1,3) = 1.

therefore:

1 = 7 - 2*3 = (-2)(3) + (1)(7).

so s = -2, and t = 1 (these are the numbers s and t i promised we could find earlier).

but clearly, -2 isn't between 0 and 6, so we have to add some multiple of 7 until it is:

-2 + 7 = 5, which IS in the desired range. so m = 5. that's the inverse we are looking for.

notice that:

3*5 = 15 = 1 + 2(7) so:

(3)(5) ≡ 1 (mod 7), so:

3^-1 (mod 7) = 5.

Quote:

---

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

---

i don't usually "double post" but i want to show that the euclidean algorithm CAN be used (without too much trouble) to find the inverse of 37 (mod 83) rather straight-forwardly:

first we need to find integers s and t such 37s + 83t = 1.

83 = 2*37 + 9
37 = 4*9 + 1
9 = 9*1 + 0

back up one step, the gcd is 1.

so...

1 = 37 - 36 = 37 - 4*9

but 9 = 83 - 74 = 83 + (-2)*37, so

1 = 37 - 4*(83 + (-2)*37) = 37 - 4*83 + 8*37 = (1 + 8)*37 - 4*83 = 9*37 + (-4)*83. so s = 9, and t = -4.

since s is in the desired range already, we have found that the inverse of 37 (mod 83) is 9.

For Soroban:
I've been doing it forever the same lazy but practical way. I never even noticed your approach. Thanks.
(Also, interestingly, that's kinda the Euclidean Algorithm in disguise. But I like your way much better than the direct algorithm.)

For Deveno:
Yes, but I've always hated actually working through the Euclidean Algorithm! I'm lazy, and for some reason it seems to demand an inordinate amount of thought given its simplicity - for me anyway.

I really can't thank you three enough for the wonderful, long and versatile answers! I really got touched that everyone wrote how they do this in such a wonderful way. I worked through all of your answers , and now I will try the problems in the book using the different methods. Thank you all so much! :) You people are like rockstars hehe ;)

Quote:

---

Originally Posted by johnsomeone

For Soroban:
I've been doing it forever the same lazy but practical way. I never even noticed your approach. Thanks.
(Also, interestingly, that's kinda the Euclidean Algorithm in disguise. But I like your way much better than the direct algorithm.)

For Deveno:
Yes, but I've always hated actually working through the Euclidean Algorithm! I'm lazy, and for some reason it seems to demand an inordinate amount of thought given its simplicity - for me anyway.

---

before computers existed, people actually used these things. for small moduli, "guess and check" works alright, but as soon as the modulus is > 1000, it's not really practical.

as an algorithm, the euclidean algorithm (for finding a gcd) is fairly efficient: if a = bq + r, instead of finding gcd(a,b) where both and and b may be quite large, we can find gcd(r,a) instead, which means instead of looking for a number as big as a, we are only looking for a number as big as r, which is usually much smaller than a

(in practice, if r is close to a, like say a-1, it may be more convenient to deal with -a (mod n) instead. the worst case scenario is where r is around 1/2 the size of a, in which case we are reducing the size of the numbers we are working with by a factor of 2 each time, an exponential reduction in difficulty at each step).

running the euclidean algorithm "backwards" (to find the r,s with ra + sb = gcd(a,b)) takes some getting used to, and it is easy to make a "sign error" (those always trip me up!). having a calculator handy is helpful, and wolfram|alpha is great for checking your results.

i'm lazy, too! :)