Direct Proof Part II

“P if and only if Q” works by breaking the statement into two different statements “if P then Q” and “if Q then P”. We prove both of these statements as if they were the statement before.

Proposition: Let n be an integer, n is not evenly divisible by 3 if and only if n^2 -1 evenly divisible by 3.

We start by dividing this into two statements. This gives us our first statement: “if n^2-1 is evenly divisible by 3 then n is not evenly divisible by 3.”

Proof: If n is not evenly divisible by 3 then n is it will have a remainder of 1 or 2 when divided by 3. This means that if the remainder is 1 then (n-1)(n+1) is divisible by 3 since (n-1) is now a multiple of 3. If the remainder is 2 then (n+1) is now a multiple of 3 so thus (n-1)(n+1( is divisible by 3. Thus we have that if n is not evenly divisible by 3 then n is not evenly divisible by 3.

Now for the second statement: “if n^2 - 1 is evenly divisible by 3 then n is not evenly divisible by 3.”

Proof: if n^2 - 1 is divisible by 3 then this means either (n-1) is divisible by 3 or (n+1), not both since (n+1)-(n-1)=2. Now if (n+1) is divisible by 3 then n cannot be divided evenly by 3 since n will give us a remainder of 1. This means that n^2 -1 is evenly divisible by 3 then n is not evenly divisible by 3.

Now that we have proved both parts of the original statement. This means that our original statement is true.

Finally, if a theorem is a fact about a specific definition or theorem, we simply have to derive that fact from relevant definitions and theorems. Here is a quick example.

Proposition: 2 is the only even prime number.

Proof: even numbers are defined as 2n which means that for all n > 1 then 2n is a composite number which means 2 is the only even prime number.

Previous | Next

  1.  What is a proof?
  2. Direct Proof Part I
  3. Direct Proof Part II
  4. Proof by  Contradiction
  5. Proof by Induction
  6. Proof by Induction example
  7. Proof by Contrapositive
  8. Proof of Existence
  9. Proof of Uniqueness
  10. Disproof
  11. Conclusion

Filed under : Mathematics

Sharing the Wonder