Results 1 to 8 of 8
Like Tree6Thanks
  • 1 Post By johnsomeone
  • 2 Post By Soroban
  • 1 Post By Deveno
  • 1 Post By Deveno
  • 1 Post By johnsomeone

Math Help - Inverse of 3 modulo 7

  1. #1
    Member
    Joined
    Nov 2011
    Posts
    86

    Red face 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Inverse of 3 modulo 7

    Quote Originally Posted by Nora314 View Post
    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 View Post
    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.)
    Last edited by johnsomeone; October 8th 2012 at 08:40 AM.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615

    Re: Inverse of 3 modulo 7

    Hello, Nora314!

    Here is a very primitive solution.


    I need to find the inverse of 3 modulo 7.

    We have: . 3x \,\equiv\,1\text{ (mod 7)}

    This means: . 3x \:=\:1 + 7a .for some integer a.

    Solve for x\!:\;x \:=\:\frac{7a+1}{3} \quad\Rightarrow\quad x \:=\:2a + \frac{a+1}{3}

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

    The smallest case occurs when a = 2.

    Hence: . x \:=\:2(2) + \tfrac{3}{3} \quad\Rightarrow\quad x \:=\:5


    Therefore, 5 is the inverse of 3, modulo 7.
    Thanks from johnsomeone and Nora314
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697

    Re: 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(n) < 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.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697

    Re: Inverse of 3 modulo 7

    Quote Originally Posted by johnsomeone View Post
    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.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Inverse of 3 modulo 7

    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.
    Last edited by johnsomeone; October 8th 2012 at 08:48 AM.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2011
    Posts
    86

    Re: Inverse of 3 modulo 7

    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697

    Re: Inverse of 3 modulo 7

    Quote Originally Posted by johnsomeone View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] modulo inverse
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 16th 2011, 09:52 AM
  2. inverse of 4 modulo 9
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 17th 2009, 06:40 AM
  3. inverse of modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 22nd 2009, 07:03 PM
  4. Inverse Modulo
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 9th 2009, 04:46 PM
  5. (n) inverse modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 21st 2009, 10:49 AM

Search Tags


/mathhelpforum @mathhelpforum