1. Limited time only! Sign up for a free 30min personal 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!

Finding inverses in modular arithmetic

  1. Mar 29, 2015 #1
    Hey PF!

    Is there a systematic way to calculate the inverse of a number in a modular setting (modular setting? is that what I call it? lol).

    How about 108x == 1 (mod 625), wolfram alpha calculated x = 272, how could I have arrived at this number besides guess and check?
     
  2. jcsd
  3. Mar 29, 2015 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    There are two nice methods.

    The first is by applying the Bezout theorem. This states that if ##a## and ##b## are integers, then there are integers ##p## and ##q## such that ##pa+bq = \text{gcd}(a,b)##. In this case we take ##a=108## and ##b=625##. The gcd is ##1## (which is a necessary and sufficient condition for finding inverses). So we search for integers ##p## and ##q## such that ##108p + 625q=1##. Our ##p## will be the inverse (just look at the equation (mod 625)).

    How to find ##p## and ##q##? Well, we have the Euclidean algorithm for finding the gcd. So let's do that:

    ##625 = 108\cdot 5 + 85##
    ##108 = 85\cdot 1 + 23##
    ##85 = 23\cdot 3 + 16##
    ##23 = 16\cdot 1 + 7##
    ##16 = 7\cdot 2 + 2##
    ##7 = 2\cdot 3 + 1##
    See http://en.wikipedia.org/wiki/Euclidean_algorithm for the details if this is unfamiliar. So we see indeed that the gcd is ##1##. Now let us do the Euclidean algorithm in reverse:

    [tex]
    \begin{eqnarray*}
    1 & = & 7 - 2\cdot 3\\
    & = & 7 - (16 - 7\cdot 2)\cdot 3\\
    & = & 7\cdot (1 + 2\cdot 3) - 16\cdot 3\\
    & = & 7\cdot 7 - 16\cdot 3\\
    & = & (23 - 16\cdot 1)\cdot 7 - 16\cdot 3\\
    & = & 23\cdot 7 - 16\cdot (1\cdot 7 + 3)\\
    & = & 23\cdot 7 - 16\cdot 10\\
    & = & 23\cdot 7 - (85 - 23\cdot 3)\cdot 10\\
    & = & 23\cdot (7 + 3\cdot 10) - 85\cdot 10\\
    & = & 23\cdot 37 - 85\cdot 10\\
    & = & (108 - 85\cdot 1)\cdot 37 - 85\cdot 10\\
    & = & 108\cdot 37 - 85\cdot (1\cdot 37 +10)\\
    & = & 108\cdot 37 - 85\cdot 47\\
    & = & 108\cdot 37 - (625 - 108\cdot 5)\cdot 47\\
    & = & 108\cdot (37 + 5\cdot 47) - 625\cdot 47\\
    & = & 108\cdot 272 - 625\cdot 47
    \end{eqnarray*}[/tex]

    Thus we get
    [tex]1 = 108\cdot 272 - 625\cdot 47[/tex]
    Looking at this equation in (mod 625), we get ##108\cdot 272 = 1##. So the inverse of 108 is 272.

    A second method is by Euler's theorem (the generalization of Fermat's little theorem): This states that if ##\text{gcd}(a,n)=1##, then ##a^{\varphi(n)} = 1## in (mod n). In our case, we get ##108^{\varphi(625)} = 1## in (mod 625). So the inverse is ##108^{\varphi(625)-1}##. Now we need to calculate the Euler totient function ##varphi##. There are several methods, but let us use this one: http://en.wikipedia.org/wiki/Euler's_totient_function#Euler.27s_product_formula
    So since ##625 = 5^4##, we get
    [tex]\varphi(625) = 625\cdot (1 - \frac{1}{5}) = 625 - 125 = 500[/tex]
    So the inverse is ##108^{499}##. This is an easier method to calculate the inverse, but it is more annoying since it leaves us with a tough exponential to calculate. A somewhat similar method but with smaller exponential can be found here http://en.wikipedia.org/wiki/Carmichael_function
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Finding inverses in modular arithmetic
  1. Modular Inverses? (Replies: 8)

  2. Modular arithmetic (Replies: 5)

  3. Modular arithmetic (Replies: 7)

Loading...