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

Relative Primes and mod

  1. Feb 26, 2009 #1
    Hi all,
    Supppose that n > 0 and 0 < x < n are integers and x is relatively prime to n, show that there is an integer y with the property:
    x*y is congruent to 1 (mod n)

    I have attempted the following, I am not sure if I am on the right track:
    1 = xy + qn which implies 1 - xy = qn
    n|(1-xy) which implies q(1-xy) = n
    so if I divide q in the first equation i get [tex]\frac{1-xy}{q}[/tex]=n which is equal to q(1-xy)=n.

    Thanks in advance
    Last edited: Feb 26, 2009
  2. jcsd
  3. Feb 27, 2009 #2
    There you go!
    1-xy=qn implies 1-xy=0 (mod n), hence 1=xy (mod n).

    No, n|(1-xy) implies (1-xy)=kn for some k, which you already knew.
  4. Feb 28, 2009 #3
    Another way to look at this is to remember that the elements of a residue system are always less than N.

    If we look at the powers of X they must come to repeat and [tex] X^S \equiv X^T Mod N [/tex] Since X is relatively prime to N we can cancel out powers of X.

    This gives [tex]X^{S-T} \equiv 1 Mod N [/tex] Assuming S is the larger value, we can not have S-T = 1 unless X is its own inverse.

    Thus S-T = 2 or more, and [tex] X^{S-T-1} \equiv X^{-1} Mod N. [/tex]
    Last edited: Feb 28, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook