Prove that Z_n has zero divisors if n is composite, and that Z_n is a field
if n is prime.
If n is composite then there exists a,b both less than n such that n = ab. Thus
To give a concrete example,
To prove is a field whenever n is prime, one really needs to worry only about checking whether every non zero element has a multiplicative inverse. The rest of the axioms are easy to verify.
We claim that if must be a permutation of .
Observe that if two elements, say ia and ja, in S are equal then n|(i-j)a. But n is prime, which means n|a or n|(i-j). if i is not equal to j, both are positive and less than n. Thus both the conditions are impossible. Hence i=j and this establishes all the elements of S are unique.
Now observe that and S has n distinct elements. Thus there must exist a "ja" in S such that . That
Here is another way to prove that is a field.
Definition: A commutative unitary ring with (i.e. it is not trivial) is called an integral domain iff (this is referring to as having "no zero divisors").
Theorem: If is a finite integral domain then is a field.
Proof: Let . And let i.e. a non-zero element. Consider, , we argue that all these elements are distinct. Say and so or . It cannot be the first case, , therefore . We have shown that are distinct. It follows by the pigeonhole principle that this list is a permutation of the and therefore for some . We have shown that each non-zero element has a multiplicative inverse. Thus, is a field.
In order to prove your result you just need to show that is an integral domain.
This is similar to what Isomorphism did, but this is more abstract.
If where is prime we know thus, by the Euclidean Algorithm we are guaranteed the existence of such that then since we see that and thus is the inverse of in
Just thought a more constructive way of actually finding the inverse might be of interest.