1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Direct Proofs

  1. Mar 3, 2015 #1
    I wasn't sure if this went in math, or computer science. I'm posting it here, because it is for a computer science course, although it's technically mathematical proofs...

    1. The problem:
    Prove or disprove the following claim: For all integers x, y, and z, if x does not divide yz then x does not divide y and x does not divide z.

    I wrote this in logic notation first, so I have that down. What I am having difficulty with is the actual prove/disprove part. I understand the steps needed to be taken (1. Assume... etc.), but am having trouble actually applying it. There are other similar questions, but I figured if I could get some help on this question, I could figure out the other ones as well, by applying the same concept...

    Also, how do I know what to choose: prove, or disprove? In what circumstances would I attempt to prove, and in what circumstances would I attempt to disprove?

    Any help would be greatly appreciated. :)
  2. jcsd
  3. Mar 3, 2015 #2


    Staff: Mentor

    You should attempt to prove a statement only if it is true. If it is false, you should disprove it, which you can do by a single counterexample.
    An equivalent statement to the one you are given is its contrapositive: For all integers x, y, and z, if x divides y OR x divides z, then x divides yz. If you can prove that, then you will have proved the statement you're given.
  4. Mar 3, 2015 #3
    Thank you for your help!

    I have one more question: I know how to use contrapositive for an implication (P => Q becomes not(Q) => not(P)). But, I'm not sure how to do that for a statement that is not an implication.

    For example, how would I apply contraposition to this sort of claim?: All x, y, z belonging to P (prime numbers), x2 + y2 =/= z2 (for all prime numbers x, y, and z, x2 + y2 =/= z2).
  5. Mar 3, 2015 #4


    Staff: Mentor

    I assume you mean x2 and so on. You can write exponents using the X2 button at the top of the input window.

    At any rate, that is an implication; namely,
    if x, y, and z are prime numbers, then x2 + y2 ≠ z2. Now it should be easy to write the contrapositive.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted