Re: Is my proof incorrect?

Quote:

Originally Posted by

**gridvvk** I received an exam back today and one of the problems I received 3 out of 10 possible points; however, I still feel my proof is correct. So before I go debate to the TA, I would appreciate a second look on my proof.

Question: Prove that there is no perfect square a^2 which is congruent to 2 mod 4.

My proof:

Let a be an element in the set of integers. Suppose that a^2 congruent 2 mod 4. Then we have 4| a^2 - 2, which means there exists an integer k such that a^2 - 2 = 4k. a^2 = 4k - 2 = 2(2k + 1), this number is always even. So this means a^2 for any a in the set of integers must be even.

No, it doesn't. It means that there is **some** integer a such that a^2 is even. And that is certainly true.

Quote:

Consider a = 5, then a^2 = 25, but 25 is not even. This means we have reached a contradiction. Hence we can conclude no perfect square is congruent to 2 mod 4.

---------

The part "this means a^2 for any a in Z must be even" was underlined and no was written next to it. When I said "we have reached a contradiction" was also underlined and written no. So I'm skeptical to now think if what I found wasn't a contradiction, but the proof seems correct to me, so it is possible that the grader thought I was doing a proof by example.

Re: Is my proof incorrect?

Quote:

Originally Posted by

**HallsofIvy** No, it doesn't. It means that there is **some** integer a such that a^2 is even. And that is certainly true.

Why is it such a weak claim though? If we take the premise a^2 congruent 2 mod 4, doesn't it mean that every a must produce a square that is even? Why only some?

Re: Is my proof incorrect?

Re: Is my proof incorrect?

Quote:

Originally Posted by

**gridvvk** Let a be an element in the set of integers.

This sounds pretentious. Just say, "Let a be an integer".

Quote:

Originally Posted by

**gridvvk** Suppose that a^2 congruent 2 mod 4. Then we have 4| a^2 - 2, which means there exists an integer k such that a^2 - 2 = 4k. a^2 = 4k - 2 = 2(2k + 1), this number is always even. So this means a^2 for any a in the set of integers must be even.

You assumed that and concluded that is even. This means you proved the following: For every , implies is even. You have not proved this: For every , is even. You cannot arbitrarily remove an assumption that was crucial in deriving the conclusion. This is similar to how the claim, "If you give me a million dollars, I can buy a golden Lamborghini" is not the same as "I can buy a golden Lamborghini".

Also, 4k - 2 above should be 4k + 2.

Edit: If 5 were congruent to 2 mod 4, then you would indeed reach a contradiction and the proof would be fine. That is, a = 5 would be a counterexample to the proved claim, "For every , implies is even" because the premise of the implication is true (under our assumption, not in reality) and the conclusion is false. As it is, a = 5 does not contradict the proved claim.

Re: Is my proof incorrect?

Quote:

Originally Posted by

**Plato** I am not sure that I would have given you even 3 out of ten.

Consider that you Suppose that a^2 congruent 2 mod 4. That is one particular

.

You correctly shown that

must be even because

is even.

But that means

is a multiple of four. So

.

mod(a^2 , 4) = 2n, where n is an integer. So I suppose I haven't shown anything at all. What is the correct way to do is proof then? Consider two cases?

Suppose a is even then a = 2k. a^2 = 4k congruent 0 mod 4. Suppose a is odd then a = 2k + 1 = (2k + 1)^2 = 4(k^2 + k) + 1 congruent 1 mod 4. So it is never the case that a^2 congruent 2 mod 4. Is that an acceptable proof, or is there a better, more elegant way to show this?

And also, out of curiosity what would you gave it a 1 or 2, haha?

Quote:

Originally Posted by

**emakarov** This sounds pretentious. Just say, "Let a be an integer".

You assumed that

and concluded that

is even. This means you proved the following: For every

,

implies

is even. You have not proved this: For every

,

is even. You cannot arbitrarily remove an assumption that was crucial in deriving the conclusion. This is similar to how the claim, "If you give me a million dollars, I can buy a golden Lamborghini" is not the same as "I can buy a golden Lamborghini".

Also, 4k - 2 above should be 4k + 2.

Edit: If 5 were congruent to 2 mod 4, then you would indeed reach a contradiction and the proof would be fine. That is, a = 5 would be a counterexample to the proved claim, "For every

,

implies

is even" because the premise of the implication is true (under our assumption, not in reality) and the conclusion is false. As it is, a = 5 does not contradict the proved claim.

You are right it does sound weird to write it out, on the exam I wrote a (element sign) then integer sign, but I wasn't sure how to do this on this forum.

Thanks a lot for writing out the symbolic logical form, it really helped me in seeing where I went wrong. In regards to your edit, isn't it the case that I never would have found an a such that a^2 is odd and that is at the same time congruent to 2 mod 4? So my attempt was fruitless at the very beginning.

Re: Is my proof incorrect?

Quote:

Originally Posted by

**gridvvk** mod(a^2 , 4) = 2n, where n is an integer.

No, the answer Plato intended was 0. This is actually a hint about how to continue the proof. You started by assuming, towards contradiction, that and concluded that is even. But this means that is even (the product of two odd numbers is odd), so . This contradicts the assumption that .

Quote:

Originally Posted by

**gridvvk** Suppose a is even then a = 2k. a^2 = 4k congruent 0 mod 4. Suppose a is odd then a = 2k + 1 = (2k + 1)^2 = 4(k^2 + k) + 1 congruent 1 mod 4. So it is never the case that a^2 congruent 2 mod 4. Is that an acceptable proof, or is there a better, more elegant way to show this?

This is a perfectly fine proof.

Quote:

Originally Posted by

**gridvvk** In regards to your edit, isn't it the case that I never would have found an a such that a^2 is odd and that is at the same time congruent to 2 mod 4?

That's right because you have proved correctly that

implies is even. (*)

This statement is true, so there is no such that , but is odd. The only catch is that (*) is true because the premise is always false. Everything can be derived from falsehood, so this proof, while correct, does not have much value.

Re: Is my proof incorrect?

Thanks a lot everyone. Now I see where the error in my reasoning was, and how I could have correctly continued the proof. I really appreciate all the help. Thanks a lot.