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?

Quote:

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** $\displaystyle a$.

You correctly shown that $\displaystyle a$ must be even because $\displaystyle a^2$ is even.

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

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

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 $\displaystyle a$.

You correctly shown that $\displaystyle a$ must be even because $\displaystyle a^2$ is even.

But that means $\displaystyle a^2$ is a multiple of four. So $\displaystyle \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?

Quote:

Originally Posted by

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

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

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

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

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

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

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.