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 - For any integer n, n^2 - 2 is not divisible by 4.

  1. Oct 19, 2011 #1
    1. The problem statement, all variables and given/known data

    Just as the title said, I need to prove:

    For any integer n, n2 - 2 is not divisible by 4

    by the method of proof by contradiction.

    2. Relevant equations

    (Relevant by division into cases)
    Even numbers = 2k for some integer k
    Odd numbers = 2m+1 for some integer m

    3. The attempt at a solution

    1. Suppose not
    2. For any integer n, n2 -2 is divisible by 4
    3. n is either even or odd
    4. Case 1 - n is even
    5. n=2k for some integer k
    6. n2 -2=(2k)2 -2
    =4*k2 -2
    =4 (k2 - 2/4)

    At this point I know where I need to be, just don't know how to justify that I got there. What I'm basically looking for is the opposite of the closure property - some way to prove that the sum of k^2 and 2/4 is not an integer. As far as I can tell, from there, I can safely state that n^2 -2 is not divisible by 4, do the same thing for odd, and conclude that there is no integer for which n^2-2 is divisible by 4. But how do I reach the fact that k^2-2/4 isn't an integer?
     
  2. jcsd
  3. Oct 19, 2011 #2
    k is an integer, right? So what is k2? And what if you subtract 1/2 from k2's "type", do you get the same type of number or a different one?
     
  4. Oct 19, 2011 #3
    Thanks for the reply. Your post helped me find the rule that I think I can justify that k2-2 isn't an integer with. From a list of a rules and properties our class was given...

    Discrete Property of Integers - There is no integer between 0 and 1

    I'm sure the marking of justifications varies between professors, but do you think a slight rework of this idea would be sufficient reasoning to state k2-1/2 is not an integer?
    i.e.

    7. k2 is an integer (justified by step 5, closure property of integers)
    8. k2-2/4 is not an integer (justified by step 7, discrete property of integers)
     
  5. Oct 19, 2011 #4
    Looks good to me. But note that I only looked at your last question, and not the whole proof, seeing as I'm a bit strapped for time. So if someone else sees an error there, please state it, but as far as the question goes, I think your last post (closure under addition (i.e. k + k + k + ... k times), and the discrete property should suffice to justify the final step.
     
  6. Oct 19, 2011 #5
    Sounds good, I'll go with that. Thanks for the help.
     
  7. Oct 20, 2011 #6
    try this:
    if n-o is odd n²-2 is odd and then not divisible by any even number
    if n-e is even n²-x is divisible by 4 only when x is a multiple of 4

    (x²:4 = x* x:4; x² - 2 = [x * x:4] [-2:4=0.5]) n-e²-2 : 4 = k.5)
     
    Last edited: Oct 20, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by contradiction - For any integer n, n^2 - 2 is not divisible by 4.
Loading...