Proof of Prime Number: Beginner's Guide

[Black Orpheus]

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?

 

[StatusX]

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]

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.

 

[Black Orpheus]

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?

 

[d_leet]

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]

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?