1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Inverses?

  1. Oct 10, 2007 #1
    Hi is there a general formula to find the inverse modulo of "a modulo n"...
    i know its denoted as [itex]a^{-1}[/itex] and
    [itex]a.a^{-1} = 1 mod n[/itex]

    for example if a=29 and n = 78 then the inverse is 35 since: 29.35 = 1 mod 78...

    (a)
    but HOW DO U CALCULATE THE INVERSE? is there a formula?? please help me out here?

    (b)
    and how can this be used to solve 43 modulo 125, hence solve 43x = 3 mod 125

    thanks
     
  2. jcsd
  3. Oct 10, 2007 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, if you unroll the definition, you have

    ua = 1 (mod n)

    if and only if you can find a v such that

    ua + vn = 1.

    Does that look familiar at all?
     
  4. Oct 10, 2007 #3
    thats euclids theorem im guessing?

    could u show me how to calculate for a = 29 and n =78???
    so that u get the inverse of 29 as 35??
    then ill try part B and see if i can do it :) thanks
     
  5. Oct 10, 2007 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, if you mean what I think you mean... then doesn't Euclid's theorem come with an algorithm for doing computation?
     
  6. Oct 10, 2007 #5
    yea but thats for just finding HCF...
    i need to know if theres a formula for finding the inverse
    you said :

    "if and only if you can find a v such that
    ua + vn = 1."

    to do this.. do i have to manually go through all the possibilites or is there an algorithm etc? thnx :)
     
  7. Oct 10, 2007 #6
    search wikipedia or google for ``diophantine equation''. There is an algorithm.
     
  8. Oct 10, 2007 #7
    thnx :D just what i wanted :)
     
  9. Oct 11, 2007 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It is more than that - it gives a way to express the HCF of x and y as ax+by.
     
  10. Oct 11, 2007 #9
    There is another way. Using the Euler phi function, we can determine the n such that 29^n==1 Mod 78 for example. In this particular case it is 2(1-1/2)*3(1-1/3)*13(1-1/13) = 24. So that:

    [tex]29^{23}\equiv\frac{1}{29} Mod 78[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Modular Inverses?
  1. Modular Multiplication (Replies: 0)

  2. Modular arithmetic (Replies: 5)

  3. Modular Mathematics (Replies: 4)

  4. Modular arithmetic (Replies: 7)

Loading...