# Direct Proofs

Tags:
1. Mar 3, 2015

### puddipop

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. Mar 3, 2015

### 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.

3. Mar 3, 2015

### puddipop

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).

4. Mar 3, 2015

### 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