Results 1 to 8 of 8

Math Help - Help with a proof - Contrapositive or Contradiction?

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    48

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Lprdgecko View Post
    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).
    Last edited by undefined; September 24th 2010 at 08:48 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    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.

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2010
    Posts
    48
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Sep 2010
    Posts
    48
    Quote Originally Posted by undefined View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Sep 2010
    Posts
    48
    Quote Originally Posted by emakarov View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by contrapositive
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 14th 2010, 03:45 PM
  2. contrapositive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 5th 2010, 01:07 PM
  3. Simple Contrapositive Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 19th 2009, 05:03 AM
  4. Contrapositive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 27th 2009, 07:36 AM
  5. Proof by Contrapositive
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2009, 10:31 PM

Search Tags


/mathhelpforum @mathhelpforum