• Support PF! Buy your school textbooks, materials and every day products Here!

Proof by contradiction

  • Thread starter Mdhiggenz
  • Start date
  • #1
327
1

Homework Statement



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.



Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
Zondrina
Homework Helper
2,065
136

Homework Statement



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.



Homework Equations





The Attempt at a Solution


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

Factoring out 2 we have 2(2p2+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.
 
  • #3
pasmith
Homework Helper
1,738
410

Homework Statement



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.
[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?
 
  • #4
88
1
I'm curious if this is an exercise in proofs by contradiction or if you're simply making matters much harder for yourself.
 
  • #5
223
10
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.
 
  • #6
327
1
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
 
  • #7
88
1
"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)
 
  • #8
327
1
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?
 
  • #9
88
1
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.
 
  • #10
327
1
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
 
  • #11
88
1
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?
 
  • #12
327
1
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)
 
  • #13
88
1
"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?
 
  • #14
CAF123
Gold Member
2,895
88
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.
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.
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.
 

Related Threads on Proof by contradiction

  • Last Post
Replies
2
Views
648
  • Last Post
Replies
3
Views
586
  • Last Post
Replies
1
Views
396
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
11
Views
533
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
754
  • Last Post
Replies
3
Views
1K
Top