1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    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!

New to proofs - need a check

  1. Oct 4, 2013 #1
    Let q be a natural number, show that if q is not divisible by 3, then neither is q^2

    proof:

    if q is not divisible by 3 then q = 3k + 2 for some integer k
    q^2 = 4 + 3(3k^2 + 4k) = 4 + 3m for some integer m, hence q is not divisible by 3

    another case, if q = 3k + 1 for some integer k, then q^2 = 1 + 3(3k^2+2k) = 1 + 3n for some integer n, hence q^2 is not divisible by 3

    second part:

    Assuming the statement that was to be proved above, deduce that there is no rational number x satisfying x^2 = 3

    proof:

    assume there is some ration number x satisfying x^2 = 3

    we can then express x = p/q where p,q are coprime

    x^2 = p^2/q^2 = 3
    hence p^2 = 3q^2 hence p = 3m for some integer m, i.e. p is divisible by 3 ***(we proved this in the first part)***

    therefore 9m^2 = 3q^2 => q^2 = 3m^2 hence q = 3n for some integer n, hence q is also divisible by 3

    this is a condradiction as we assumed p and q were coprime, but have shown they have a factor of 3, hence there does not exist a rational number x such that x^2 = 3

    ok, is this proof OK? the part I have labelled *** ("***(we proved this in the first part)***") is it true that we proved this in the first part, as we proved that if a natural number is not divisible by 3, then neither is it's square, but in this proof, I am saying if it's square is divisible by 3, then the number is divisible by 3 - is this the same thing (I think it is)
     
  2. jcsd
  3. Oct 4, 2013 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The proof looks fine.... as a formatting thing instead of adding at the end of a line (we proved this in the first part), I would put at the start of the line "by part one,". For example

    "hence p^2 = 3q^2 hence p = 3m for some integer m" becomes
    "hence p^2 = 3q^2, so by part one p=3m for some integer m"
     
  4. Oct 4, 2013 #3
    thanks, so proving that q is not divisible by 3 then neither is q^2 is the same thing as proving if q^2 = 3m (i.e. divisible by 3) then so is q?
     
  5. Oct 4, 2013 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, that's called the contrapositive and is often useful. If you have two statements , A and B, then proving if A then B is the same as proving if not B, then not A.

    In your case you have A is "q is not divisible by 3", and B is "q2 is not divisible by 3". You proved if A, then B, so you get for free if not B, then not A.

    not B is (after cancelling a double negative)"q2 is divisible by 3" and not A is "q is divisible by 3"
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: New to proofs - need a check
  1. Check my three proofs (Replies: 2)

  2. Check my proof (Replies: 5)

Loading...