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