1. Limited time only! Sign up for a free 30min personal 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!

Proof by contradiction

  1. Sep 14, 2013 #1
    1. The problem statement, all variables and given/known data

    Hello Guys, can you check my proof.

    Problem statement: Let n be an integer such that n2 is even. Prove that n2 is divisible by 4.

    Proof by contradiction:

    Suppose n2 is not divisible by 4, thus n is odd. Such that n=2p+1, and n2=4p2+4p+1. Factoring out 2 we have 2(2p2+2p+.5) which is even, and divisible by 4. Thus we have a contradiction. End of proof.



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Sep 14, 2013 #2

    Zondrina

    User Avatar
    Homework Helper


    That's the general idea, just pointing this out though :

    You're working with integers, not rationals. It looks to me ##n## is still odd there, so you're not done quite yet.
     
  4. Sep 14, 2013 #3

    pasmith

    User Avatar
    Homework Helper

    [itex]2p^2 + 2p + \frac12[/itex] is not an integer. In fact [itex]4p^2 + 4p + 1 = 2(2p^2 + 2p) + 1[/itex] is odd. Also the assumption that if [itex]n^2[/itex] is not divisible by 4 then [itex]n[/itex] is odd is circular: it's the contrapositive of the statement you are asked to prove.

    What you have shown is that if [itex]n[/itex] is odd, then [itex]n^2[/itex] is odd. So what must [itex]n[/itex] be if [itex]n^2[/itex] is even?
     
  5. Sep 14, 2013 #4
    I'm curious if this is an exercise in proofs by contradiction or if you're simply making matters much harder for yourself.
     
  6. Sep 14, 2013 #5
    Check out divisibility rules and fit that condition in your proof. Right now you took the echelon form of an odd integer and showed that any odd*odd operation yields an odd result and it had nothing to do with divisibility by 4.
     
  7. Sep 14, 2013 #6
    Thank you for all the replies.

    I noticed that a proof by contradiction might have been the worst way to go. So I tried two different methods direct, and contrapositive.

    1. Direct: First I rewrote the problem if n2 is even then n2 is divisble by 4.

    since n2 is even, then n2=2R, where are is any integer, and n=√2R, and I got stuck.


    2. Proof by contrapositive.

    4 is not divisible by n then n2 is odd.

    Proof: Suppose 4 is not divisible by n , this means that n is odd, such that n=2n+1

    n2=2(2n2+2n)+1 which is also odd.

    end of proof.


    A few questions. can I assume that if n is not divisible by 4 then it must be odd? I kind of used a bit of common sense for that. " I could be wrong"


    Thank you

    Higgenz
     
  8. Sep 14, 2013 #7
    "can I assume that if n is not divisible by 4 then it must be odd?" no. take 2 for example.

    You need to think just a step more. If n^2 is even, then what is n - even, odd or both? -- Does that help you? (hint: it does)
     
  9. Sep 14, 2013 #8
    If n^2, n is even. I can prove that simply by,

    Suppose n is even, then n=2R where R is any integer.

    n^2=4R^2=2(2R^2) which is also even.

    Oh So would I have to do a sub step, and prove that if n is odd, then n^2 is odd?
     
  10. Sep 14, 2013 #9
    Exactly. You want to show that n^2 is even iff (if and only if) n is even. With that done, you're almost there.
     
  11. Sep 14, 2013 #10
    I get what you're saying, but i'm confused on how to express that. From the other post I started with n is even, then n^2 is even. So now I have to start if n^2 is even then n is even.

    n2 is even, then n2=2R.

    and n=√2R , where R is any integer. This is rational so I'm not sure how this will help my case.

    Also how did you know that it would be an if and only if proof?

    Thanks
     
  12. Sep 14, 2013 #11
    I knew because I did it.

    I want you to be in on this with me. We want to show that if n^2 is even, then it is a multiple of 4.

    I'm just looking for possibilities, basically. So we look to see, if we can say anything about n if n^2 is even. Turns out we can. There are two possibilities, right? -- n can be odd or even. If n is even, say n=2m, then n^2 = 4m^2, which is obviously even.

    If n is odd, say n=2m+1, then what?

    How does that help us?
     
  13. Sep 14, 2013 #12
    If n is odd n^2 would be odd as well. n2=2(2R2+2R)+1 n=2R+1

    That tells us that even ^2 gives you even, and odd squared gives you odd.

    It helps us because it tells us something directly about n, for instance since they are telling us explicitly that n^2 is even. We know that n is even as well. Which we can then deduce that n is divisible by 4 since 2n=4*r=2(4*r)
     
  14. Sep 14, 2013 #13
    "Which we can then deduce that n is divisible by 4 since 2n=4*r=2(4*r)"
    I'm not sure where you're going here, or if you miss typed.
    You want to deduce something about n^2, right?
     
  15. Sep 15, 2013 #14

    CAF123

    User Avatar
    Gold Member

    If n2=2R, then n = ±√2R with R in the naturals. For √2R to be an integer, 2R must be a perfect square. All perfect squares you obtain are divisible by 2 and it is then easy to prove that they are all divisible by 4. This is a more direct approach.
     
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: Proof by contradiction
  1. Proof By Contradiction (Replies: 7)

  2. Proof by contradiction (Replies: 1)

  3. Proof by Contradiction (Replies: 1)

Loading...