# Proof by contradiction - For any integer n, n^2 - 2 is not divisible by 4.

1. Oct 19, 2011

### Greywolfe1982

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. Oct 19, 2011

### Ryker

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?

3. Oct 19, 2011

### Greywolfe1982

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)

4. Oct 19, 2011

### Ryker

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.

5. Oct 19, 2011

### Greywolfe1982

Sounds good, I'll go with that. Thanks for the help.

6. Oct 20, 2011

### logics

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