Results 1 to 4 of 4

Math Help - inverse of 4 modulo 9

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    inverse of 4 modulo 9

    I have tried to follow the previous posts and I'm still confused.
    I can follow the Euclidean algorithm to find gcd and I know that gcd has to equal 1 for there to be an inverse, in other words a and m have to be relatively prime, but could someone lay out the steps? Let a=4 and m=9.

    Then 9 = 2(4) + 1
    and 4 = 4(1) + 0

    so 1 = 9 - 2(4)

    Then do you set 4p = 1 (mod 9) ?

    I really don't understand how the process (algorithm) continues.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Inverses in modular arithmetic

    Hello oldguynewstudent
    Quote Originally Posted by oldguynewstudent View Post
    I have tried to follow the previous posts and I'm still confused.
    I can follow the Euclidean algorithm to find gcd and I know that gcd has to equal 1 for there to be an inverse, in other words a and m have to be relatively prime, but could someone lay out the steps? Let a=4 and m=9.

    Then 9 = 2(4) + 1
    and 4 = 4(1) + 0

    so 1 = 9 - 2(4)

    Then do you set 4p = 1 (mod 9) ?

    I really don't understand how the process (algorithm) continues.
    You're correct in what you have so far. Let me summarise:

    The problem is to find the value(s) of p for which 4p\equiv1\mod9; in other words the value(s) of p for which:
    4p+9q=1, where q is another integer
    You have correctly found, using the Euclidean Algorithm, that
    4\times (-2)+9\times1 = 1
    So you have the solution
    p=-2, q=1
    So you have, in fact, found an inverse of 4 \mod 9, and that is -2. Check it out:
    4\times(-2) = -8 \equiv 1 \mod9
    But perhaps you were looking for an inverse between 0 and 8. So you simply add enough 9's to your solution until you get a value in this range. This works because
    -2 + 9n \equiv -2 \mod 9 for any integer n
    Of course, all you need to add is 9 itself, and get -2+9=7. So 7 is also an inverse of 4. Check this one out:
    4\times7=28\equiv1 \mod9
    This gives us another solution to the equation
    4p+9q=1
    and that is
    p=7,q=-3
    There are infinitely many others that you can find in a similar way: p=16, q=-7;\quad p=-11, q = 5,...etc.

    Does that help to clear things up?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Quote Originally Posted by Grandad View Post
    Hello oldguynewstudentYou're correct in what you have so far. Let me summarise:

    The problem is to find the value(s) of p for which 4p\equiv1\mod9; in other words the value(s) of p for which:
    4p+9q=1, where q is another integer
    You have correctly found, using the Euclidean Algorithm, that
    4\times (-2)+9\times1 = 1
    So you have the solution
    p=-2, q=1
    So you have, in fact, found an inverse of 4 \mod 9, and that is -2. Check it out:
    4\times(-2) = -8 \equiv 1 \mod9
    But perhaps you were looking for an inverse between 0 and 8. So you simply add enough 9's to your solution until you get a value in this range. This works because
    -2 + 9n \equiv -2 \mod 9 for any integer n
    Of course, all you need to add is 9 itself, and get -2+9=7. So 7 is also an inverse of 4. Check this one out:
    4\times7=28\equiv1 \mod9
    This gives us another solution to the equation
    4p+9q=1
    and that is
    p=7,q=-3
    There are infinitely many others that you can find in a similar way: p=16, q=-7;\quad p=-11, q = 5,...etc.

    Does that help to clear things up?

    Grandad
    Wow! How did you make it so simple when my professor filled up 3 blackboards with infinite tangeants. This was immensely helpful!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    A little more explicitly than Grandad so nicely put. If x_0 is a solution to ax\equiv 1\text{ mod }n then any element of X=\left\{x\in\mathbb{Z}:x=x_0+nz\quad z\in\mathbb{Z}\right\} is a solution. For let \xi\in X then a\xi=a(x_0+nz)=ax_0+anz\equiv ax+0\equiv1+0=1\text{ mod }n
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] inverse in modulo 26
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 9th 2011, 02:52 PM
  2. [SOLVED] modulo inverse
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 16th 2011, 10:52 AM
  3. inverse of modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 22nd 2009, 08:03 PM
  4. Inverse Modulo
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 9th 2009, 05:46 PM
  5. (n) inverse modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 21st 2009, 11:49 AM

Search Tags


/mathhelpforum @mathhelpforum