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

Mod(prime) is a field mod(non-prime) is not

  1. Oct 14, 2011 #1
    Now, I can show that if n is prime then Z/Zn is a field

    a = a
    b = an-2

    a*b = an-1 = 1 (mod n) --> Fermat's little theorem

    However, I can't really seem to show that there is no multiplicative inverse for Z/Zn where n is not prime.

    First question: a =/=b correct?

    i know that there is the whole if gcd(a,n) = 1 then there is a multiplicative inverse, but I can't really see how to leverage this fact.

    Any help would be much appreciated.
     
  2. jcsd
  3. Oct 14, 2011 #2
    Not only that, but I don't truly understand why this is.
     
  4. Oct 14, 2011 #3

    Deveno

    User Avatar
    Science Advisor

    for non-prime n,

    what you want to do is find a,b ≠ 0 in Z/Zn such that:

    ab = 0 (mod n).

    these elements cannot be invertible.

    suppose 1/a existed. then:

    (1/a)(ab) = [(1/a)(a)]b = 1b = b ≠ 0 (mod n)

    BUT....

    (1/a)(ab) = (1/a)0 = 0 (mod n), a contradiction.

    (1/b) can be shown not to exist in a similar fashion (multiply on the right).

    since n is not prime, there is some 1 < d < n with d|n.

    so n = dk, where 1 < d,k < n.

    thus d,k ≠ 0 (mod n) but dk = n = 0 (mod n).
     
  5. Oct 14, 2011 #4
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook