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

1. Oct 14, 2011

### General_Sax

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. Oct 14, 2011

### General_Sax

Not only that, but I don't truly understand why this is.

3. Oct 14, 2011

### Deveno

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

4. Oct 14, 2011

Thanks