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

Cryptography / Number Theory

  1. Feb 24, 2010 #1
    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.
  2. jcsd
  3. Feb 24, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook