Cryptography / Number Theory

  • #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.
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
 

Related Threads on Cryptography / Number Theory

  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
1K
Top