# Help with a proof - Contrapositive or Contradiction?

• Sep 23rd 2010, 06:04 PM
Lprdgecko
Help with a proof - Contrapositive or Contradiction?
I feel like I've been asking a lot of questions on here lately, but I really don't know where to start on this proof.

The statement is "Let q be a positive integer such that q is greater than or equal to 2 and such that for any integers a and b, if q|ab then q|a or q|b. Show that q is a prime number."

My first thought was to use a proof by contradiction, but I'm pretty sure my professor suggested us to do a proof by contrapositive, though I may have misunderstood him. I tried doing it by contrapositive, but I'm not sure if what I have so far is correct:

We proceed by way of contrapositive. Assume that if q is a composite number, then q is a positive integer greater than or equal to 2 such that there exist integers a and b for which if q does not divide ab then q does not divide a and q does not divide b.

If this is correct, where do I go from here? If it's not correct, what did I do wrong? Also - would doing a proof by contradiction be simpler?
• Sep 23rd 2010, 08:14 PM
aman_cc
You are correct to approach on contradiction lines. I think that would be the easiest for this problem.
Hint - Let q not be a prime

then q = x.y where 1<x,y<q

What can you say about q|xy, q|x and q|y?
• Sep 23rd 2010, 09:41 PM
undefined
Quote:

Originally Posted by Lprdgecko
I feel like I've been asking a lot of questions on here lately, but I really don't know where to start on this proof.

The statement is "Let q be a positive integer such that q is greater than or equal to 2 and such that for any integers a and b, if q|ab then q|a or q|b. Show that q is a prime number."

My first thought was to use a proof by contradiction, but I'm pretty sure my professor suggested us to do a proof by contrapositive, though I may have misunderstood him. I tried doing it by contrapositive, but I'm not sure if what I have so far is correct:

We proceed by way of contrapositive. Assume that if q is a composite number, then q is a positive integer greater than or equal to 2 such that there exist integers a and b for which if q does not divide ab then q does not divide a and q does not divide b.

If this is correct, where do I go from here? If it's not correct, what did I do wrong? Also - would doing a proof by contradiction be simpler?

I think you got mixed up while writing the part I marked in red. Proving by contrapositive means: you assume the negation of the conclusion but do not assume anything about the premise. You then proceed to prove the premise is false.

So instead write something like, Assume q is not prime; then there exist integers x, y with x>1 and y>1 such that q=xy. Now consider what happens when we let a=x and b=y...

That is if you want to prove by contrapositive; contradiction is fine too.

Additional note: If you have a proof of the contrapositive, then you can easily transform this into a proof by contradiction just by assuming the premise, call it u, is true and the conclusion is false and then ending up with the contradiction (u and not u).
• Sep 23rd 2010, 10:29 PM
emakarov
I agree. Proofs by contrapositive and by contradiction are closely related. To remind, a contrapositive of P -> Q is ~Q -> ~P. A statement and its contrapositive are equivalent, so instead of one it is possible to prove the other. In a proof by contradiction, instead of proving Q one shows ~Q -> F where F is falsehood; then Q follows.

Formally, proving P -> Q in this way involves both proof by contrapositive and proof by contradiction. Namely, one assumes P and then proves Q by contradiction. For this, one assumes ~Q and from here derives ~P (this is the contrapositive of P -> Q). Combining ~P with the first assumption P gives falsehood, so Q follows.

In practice, the names "proof by contrapositive" and "proof by contradiction" are often used interchangeably.

Quote:

Assume that if q is a composite number, then q is a positive integer greater than or equal to 2 such that there exist integers a and b for which if q does not divide ab then q does not divide a and q does not divide b.
Even though the original problem starts with a universal quantification and implication: "For all q, if q >= 2, then ...", this beginning is not usually used in the contrapositive. Namely, we don't prove things like, "For all q, if ..., then q < 2". The problem has a preamble, so to speak: Let q be a positive integer such that q >= 2. This preamble is simply assumed. The rest is a (nested) implication: "Suppose that for any integers a and b, if q|ab then q|a or q|b; then q is a prime number." It is this implication that is proved by contrapositive/contradiction.
• Sep 24th 2010, 08:24 AM
Lprdgecko
Thank you all for the help. Unfortunately, I had gone to bed before I was able to see your replies (I have already turned in the homework. I just left what I had written down), but they are helpful. We worked out that problem in class this morning and a lot of my classmates were confused on that one, as well. What caught me off guard was the fact that there seemed to be two "if, then" statements, but really there was only one... But the professor explained how to do it in class and your tips are also helpful. I'll look at that problem again before our test next week.
• Sep 24th 2010, 08:26 AM
Lprdgecko
Quote:

Originally Posted by undefined
I think you got mixed up while writing the part I marked in red. Proving my contrapositive means: you assume the negation of the conclusion but do not assume anything about the premise. You then proceed to prove the premise is false.

So instead write something like, Assume q is not prime; then there exist integers x, y with x>1 and y>1 such that q=xy. Now consider what happens when we let a=x and b=y...

That is if you want to prove by contrapositive; contradiction is fine too.

Additional note: If you have a proof of the contrapositive, then you can easily transform this into a proof by contradiction just by assuming the premise, call it u, is true and the conclusion is false and then ending up with the contradiction (u and not u).

So, in a proof by contrapositive, I don't actually state the entire contrapositive at the beginning - just the ~Q part, then I prove ~P, right?
• Sep 24th 2010, 08:39 AM
emakarov
Right, if by "state" you mean "assume". You can state the entire contrapositive ~Q -> ~P as something you have to prove. In proving it, you assume ~Q and prove ~P.
• Sep 24th 2010, 08:41 AM
Lprdgecko
Quote:

Originally Posted by emakarov
Right, if by "state" you mean "assume". You can state the entire contrapositive ~Q -> ~P as something you have to prove. In proving it, you assume ~Q and prove ~P.

Oh ok. I understand now. Thanks!