• Support PF! Buy your school textbooks, materials and every day products Here!

Prime Number Proof

1. Here is the problem I'm stuck on:

Let q be a positive integer, q is greater than or equal to 2, let a and b be integers such that if q divides ab, then q divides a or q divides b. Show that q is a prime number.




2. I know that q is prime if and only if 1 divides q and q divides q.



3. I don't really know where to begin. Where might I go from here?
 

Answers and Replies

StatusX
Homework Helper
2,563
1
You want to show that if q is such that whenever q divides ab, q divides a or q divides b, then q must be prime. One way to do this is to show that if q is not prime, then it is not true that whenever q divides ab, q divides a or q divides b. Do you see why this is the same thing? This is called the contrapositive of the original statement.
 
HallsofIvy
Science Advisor
Homework Helper
41,736
894
Notice that "if q divides ab then q divides a or q divides b" must be true for all numbers a, b. Suppose q was not prime. Can you use that to construct numbers a, b such that "q divides ab but q does not divide a or b separately". The easiest case to try is q= 6.
 
Last edited by a moderator:
If I assume that q is prime, then that implies that there exist two integers ab such that q divides ab. It also must mean that a and b are both greater than 1 and less than q. If this is the case, then q does not divide a and q does not divide b (contrapositive: if q is not prime, then q divides ab implies q does not divide a and q does not divide b). Therefore p is prime?
 
1,073
1
2. I know that q is prime if and only if 1 divides q and q divides q.
Just to nitpick a little bit (maybe a lot..) that definition can't be exactly right since it is trivially true for all integers.

In other words it is true for all integers n that 1|n and n|n. You need to modify the definition to say something along the lines of that 1 and n are the only divisors or n, and n is not equal to 1.
 
HallsofIvy
Science Advisor
Homework Helper
41,736
894
If I assume that q is prime, then that implies that there exist two integers ab such that q divides ab.
??Given any integer q, there certainly exist many integers a, b such that q divides ab. That's not the point!

It also must mean that a and b are both greater than 1 and less than q.
No, there is nothing said here requiring that a and b be less than q. Indeed, if q divides either a or b, then one of them must be at least as large as q.

If this is the case, then q does not divide a and q does not divide b (contrapositive: if q is not prime, then q divides ab implies q does not divide a and q does not divide b). Therefore p is prime?
?? Where did p come from?? Did you mean "q". If so, you started by saying "If I assume q is prime". What you have proved is "If q is prime, then q is prime"! No, what you give is not the contrapositive of the statement you want to prove- because the statement you give is NOT true.

One more time- you have misstated the problem itself:
Let q be a positive integer, q is greater than or equal to 2, let a and b be integers such that if q divides ab, then q divides a or q divides b. Show that q is a prime number.
is not true.
For example q= 6 is NOT a prime number but a= 5, b= 12 are numbers such that "if q (6) divides ab (60) then q divides a or q divides b (6 divides 12)".

What you want to prove is
Let q be a positive integer, q is greater than or equal to 2, such that for any integers, a, b, such that q divides ab, then q divides a or q divides b. Show that q is a prime number.
As you have been told, it is sufficient to prove the "contrapositive": "if there exist integers a,b such that q divides ab but q does not divide either a or b." Suppose q= 6. Can you find a, b such that 6 divides ab but does not divide either a or b?
 
Last edited by a moderator:

Related Threads for: Prime Number Proof

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
12K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
10
Views
3K
Replies
6
Views
654
  • Last Post
Replies
12
Views
1K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
7
Views
903
Top