Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Chinese Remainder Theorem, Solving For Multiplicative Inverses

  1. Mar 10, 2010 #1
    So I am working on solving sets of linear congruence with the chinese remainder theorem. When I go to solve for the inverses I am meeting a bit of trouble. What do I do when the a term is larger that m?
    Example
    77x=1(mod3)
    33y=1(mod7)
    21z=1(mod11)
    where x,y,z are the inverses I am trying to solve for so I can use the chinese remainder thm. I usually solve for congruences by applying the euclidean algorithm backwards, but I have never encountered the situation where the a term is larger than the modulo m.... What do I do to solve for these inverses?

    Also, I am looking at a system of linear congruences like the following
    N=0(mod[tex]\phi[/tex]1)
    N=-1(mod[tex]\phi[/tex]2)
    ...
    N=-(n-1)(mod[tex]\phi[/tex]n)
    A unique solution exists since ([tex]\phi[/tex]n,[tex]\phi[/tex]m)=1 whenever m does not equal n.
    So it asks when n=2 what is the least possible value of N? How do I do this/ solve for the inverses? I didn't think it was referring to phi of n or phi of m more like phi sub n or phi sub m, but I am not entirely sure...
     
  2. jcsd
  3. Mar 10, 2010 #2
    A hint for your first question:

    If a = b (mod m), then ax = bx (mod m).

    Find a way to apply this to, say, the equation 77x = 1 (mod 3).

    HTH

    Petek
     
  4. Mar 10, 2010 #3
    the answer to the first part is that you can always subtract 0 mod m from both sides. Therefore since 75x = 0 mod 3, 77x-75x =1-0 mod 3. the answer to the second part is to look for a recursive method to find N then see if that can be reduced to a direct formula as a function of n . The simple answer to the second part is different depending upon whether N is an negative or positive number. Assuming N is positive and n = 5 the second smallest number N would be 61.
     
    Last edited: Mar 10, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook