# Thread: Is my proof incorrect?

1. ## Is my proof incorrect?

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. 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.

2. ## Re: Is my proof incorrect?

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.

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.

3. ## Re: Is my proof incorrect?

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?

4. ## Re: Is my proof incorrect?

Originally Posted by gridvvk
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 itegers. 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. 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.
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 $a$.
You correctly shown that $a$ must be even because $a^2$ is even.

But that means $a^2$ is a multiple of four. So $\mod(a^2,4)=~?$.

5. ## Re: Is my proof incorrect?

Originally Posted by gridvvk
Let a be an element in the set of integers.
This sounds pretentious. Just say, "Let a be an integer".

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 $a^2\equiv 2\pmod{4}$ and concluded that $a^2$ is even. This means you proved the following: For every $a\in\mathbb{Z}$, $a^2\equiv 2\pmod{4}$ implies $a^2$ is even. You have not proved this: For every $a\in\mathbb{Z}$, $a^2$ 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 $a\in\mathbb{Z}$, $a^2\equiv 2\pmod{4}$ implies $a^2$ 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.

6. ## Re: Is my proof incorrect?

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 $a$.
You correctly shown that $a$ must be even because $a^2$ is even.

But that means $a^2$ is a multiple of four. So $\mod(a^2,4)=~?$.
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?

Originally Posted by emakarov
This sounds pretentious. Just say, "Let a be an integer".

You assumed that $a^2\equiv 2\pmod{4}$ and concluded that $a^2$ is even. This means you proved the following: For every $a\in\mathbb{Z}$, $a^2\equiv 2\pmod{4}$ implies $a^2$ is even. You have not proved this: For every $a\in\mathbb{Z}$, $a^2$ 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 $a\in\mathbb{Z}$, $a^2\equiv 2\pmod{4}$ implies $a^2$ 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.

7. ## Re: Is my proof incorrect?

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 $a^2\equiv 2\pmod{4}$ and concluded that $a^2$ is even. But this means that $a$ is even (the product of two odd numbers is odd), so $a^2\equiv0\pmod{4}$. This contradicts the assumption that $a^2\equiv 2\pmod{4}$.

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.

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

$a^2\equiv 2\pmod{4}$ implies $a^2$ is even. (*)

This statement is true, so there is no $a$ such that $a^2\equiv 2\pmod{4}$, but $a^2$ 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.

8. ## 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.