Results 1 to 7 of 7

Math Help - Solve by finding an inverse for 7

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Solve by finding an inverse for 7

    Solve 7x = 11 mod 9 by finding an inverse for 7. (= is congruence not equality)

    I'm trying to do this by using the euclidean algorithm:

    9 = 1(7) + 2
    7 = 2(3) + 1
    3 = 1(3) + 0

    If have done the above correctly, How do I use this to find the inverse of 7?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2010
    Posts
    8
    notice 7\times4=28\equiv 1\pmod{9}
    then 11\times4=44\equiv 8\pmod{9}

    so x\equiv 8\pmod{9}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    I still don't get it...

    Why 7x4...? Is that arbitrary?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by jzellt View Post
    I still don't get it...

    Why 7x4...? Is that arbitrary?
    Well, in this case the best method involves trial and error.

    Since (7,9)=1, then 7 has a multiplicative inverse modulo 9. That inverse is a positive integer greater than 1 and less than 9, and it is coprime to 9. So, we have just a few possibilities: 2,4,5,7,8. Let's try them, one by one:

    2\times 7=14\equiv 5\pmod{9}

    4\times 7=28\equiv 1\pmod{9}

    And we can stop there. So 4\equiv 7^{-1}\pmod{9}, which means

    4\times 7x\equiv 4\times 11\pmod{9},

    or, equivalently,

    x\equiv 8\pmod{9}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Why would you want to solve 7x \equiv 11 \pmod{9} to find an inverse for 7 modulo 9 ? Let's do it together :

    Aim : find the inverse of 7 modulo 9.
    Mathematical aim : solve x \equiv \frac{1}{7} \pmod{9}, that is, solve 7x \equiv 1 \pmod{9} for x.

    gcd(7, 9) = 1. Good, we know an inverse exists.

    Can you use the Euclidian Algorithm on 7x \equiv 1 \pmod{9} to solve for x and hence find the inverse of 7 modulo 9 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Is 7 \times 4 = 28 = 1 \pmod{9} so that the inverse of 7 \pmod{9} is 4 ...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,368
    Thanks
    1313
    7x= 1 (mod 9) means that 7x= 9n+ 1 for some integer n.

    That is the same as 7x- 9n= 1.

    7 divides into 9 once with remainder 2: 9- 7= 2.
    2 divides into 7 3 times with remainder 1: 7- 3(2)= 1.

    Replacing that "2" with "9- 7", 7- 3(9- 7)= 4(7)- 3(9)= 1.

    Once solution is x= 4, n= -3 which is enough to tell us that 1/7= 4 (mod 9)

    Of course, it would be jjust as simple to solve 7x= 11= 2 (mod 9) directly:
    7x= 2 (mod 9) means 7x= 9n+ 2 for some integer n. Once we have arrived at 4(7)- 3(9)= 1, multiplying both sides of the equation by 2, (8)(7)- 6(9)= 2 so that x= 8 satisfies 7x= 2 (mod 9).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How to solve inverse function?
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: November 20th 2011, 02:17 PM
  2. Solve inverse tan integral
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 8th 2009, 02:35 PM
  3. inverse trig values and finding inverse
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: April 6th 2009, 12:04 AM
  4. solve w/o calc inverse of tan -1 and for sin,cos
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: August 16th 2008, 03:06 PM
  5. Replies: 1
    Last Post: January 17th 2008, 02:35 AM

Search Tags


/mathhelpforum @mathhelpforum