Cryptography / Number Theory

[guyfromnola]

I'm having some trouble addressing the following two questions in a text I am going through:

1. Show that n is a prime number iff whenever a,b ∈ Zn with ab=0, we must have that a=0 or b=0.

2. Show that n is a prime number iff for every a,b,c ∈ Zn satisfying a not =0, and ab=ac, we have that b=c.

There were some other similar questions that addressed showing two numbers are relatively prime by showing that gcd(a,n)=1, which was a little difficult to start, but I think I managed to get through them. However, I am stuck with these. Not sure how to begin to prove.

Any help is appreciated.

 

[CRGreathouse]

However, I am stuck with these. Not sure how to begin to prove.

Begin by expanding the definitions.

For 1:
ab = 0 (mod n) exactly when n | ab
a = 0 (mod n) exactly when n | a
b = 0 (mod n) exactly when n | b

So the question becomes:
Show that n is a prime number iff whenever n | ab, we must have that n | a or n | b.

That is, you need to show:
a. If n is prime and n | ab, either n | a or n | b.
b. If n is not prime, then there is some pair (a, b) with n ∤ a, n ∤ b, and n | ab.