Results 1 to 8 of 8
Like Tree4Thanks
  • 1 Post By HallsofIvy
  • 1 Post By Plato
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Is my proof incorrect?

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Jupiter
    Posts
    20

    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.
    Last edited by gridvvk; April 23rd 2013 at 01:06 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,004
    Thanks
    1660

    Re: Is my proof incorrect?

    Quote Originally Posted by gridvvk View Post
    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.
    Thanks from gridvvk
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2013
    From
    Jupiter
    Posts
    20

    Re: Is my proof incorrect?

    Quote Originally Posted by HallsofIvy View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,803
    Thanks
    1692
    Awards
    1

    Re: Is my proof incorrect?

    Quote Originally Posted by gridvvk View Post
    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)=~?.
    Thanks from gridvvk
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781

    Re: Is my proof incorrect?

    Quote Originally Posted by gridvvk View Post
    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 View Post
    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.
    Last edited by emakarov; April 23rd 2013 at 01:32 PM.
    Thanks from gridvvk
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2013
    From
    Jupiter
    Posts
    20

    Re: Is my proof incorrect?

    Quote Originally Posted by Plato View Post
    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?

    Quote Originally Posted by emakarov View Post
    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.
    Last edited by gridvvk; April 23rd 2013 at 01:50 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781

    Re: Is my proof incorrect?

    Quote Originally Posted by gridvvk View Post
    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}.

    Quote Originally Posted by gridvvk View Post
    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 View Post
    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.
    Thanks from gridvvk
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jan 2013
    From
    Jupiter
    Posts
    20

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Evaluating an incorrect proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2012, 06:35 PM
  2. incorrect proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 8th 2010, 02:15 PM
  3. Incorrect equation, please help me fix it.
    Posted in the Algebra Forum
    Replies: 7
    Last Post: August 14th 2009, 04:48 AM
  4. Incorrect Logarithm, please help me fix it.
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 14th 2009, 01:15 AM
  5. Incorrect integral
    Posted in the Calculus Forum
    Replies: 5
    Last Post: June 18th 2009, 10:26 AM

Search Tags


/mathhelpforum @mathhelpforum