Proving n^2 is Divisible by 4: Contradiction Method

[Mdhiggenz]

Homework Statement

Hello Guys, can you check my proof.

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

Proof by contradiction:

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

Homework Equations

The Attempt at a Solution

 

[STEMucator]

Homework Statement

Hello Guys, can you check my proof.

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

Proof by contradiction:

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

Homework Equations

The Attempt at a Solution

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

Factoring out 2 we have 2(2p²+2p) +1 which is odd, [STRIKE]and divisible by 4[/STRIKE].

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

 

[pasmith]

Homework Statement

Hello Guys, can you check my proof.

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

Proof by contradiction:

Suppose n² is not divisible by 4, thus n is odd. Such that n=2p+1, and n²=4p²+4p+1. Factoring out 2 we have 2(2p²+2p+.5) which is even, and divisible by 4.

[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?

 

[jeppetrost]

I'm curious if this is an exercise in proofs by contradiction or if you're simply making matters much harder for yourself.

 

[lendav_rott]

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.

 

[Mdhiggenz]

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 n² is even then n² is divisble by 4.

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


2. Proof by contrapositive.

4 is not divisible by n then n² is odd.

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

n²=2(2n²+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

 

[jeppetrost]

"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)

 

[Mdhiggenz]

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?

 

[jeppetrost]

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.

 

[Mdhiggenz]

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.

n² is even, then n²=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

 

[jeppetrost]

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?

 

[Mdhiggenz]

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)

 

[jeppetrost]

"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?

 

[CAF123]

First I rewrote the problem if n² is even then n² is divisble by 4.

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

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.

n² is even, then n²=2R.

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

If n²=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.