Page 1 of 2 12 LastLast
Results 1 to 15 of 24
Like Tree3Thanks

Math Help - If x + y is odd for integers x and y, then x * y is even?

  1. #1
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    69
    Thanks
    1

    If x + y is odd for integers x and y, then x * y is even?

    Prove the following statement:

    If x + y is odd for integers x and y, then x * y is even

    My response:

    If the sum of two numbers is odd, then their product is even.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: If x + y is odd for integers x and y, then x * y is even?

    Quote Originally Posted by lamentofking View Post
    Prove the following statement:

    If x + y is odd for integers x and y, then x * y is even

    My response:

    If the sum of two numbers is odd, then their product is even.
    That doesn't constitute as "proof" of the statement.

    Firstly, note that an odd number will always have the form 2n - 1, \ n \in \mathbb{Z^{+}} and an even number of the form 2m, \ m \in \mathbb{Z^{+}}.

    You have to first prove that x+y will be odd iff x is odd and y is even or y is odd and x is even. Then prove that their product must be even i.e. xy \equiv 0 \pmod{2}.
    Last edited by FelixFelicis28; September 5th 2013 at 05:22 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    69
    Thanks
    1

    Re: If x + y is odd for integers x and y, then x * y is even?

    So could I say, "if the sum is odd, then either m is odd and n is even or m is even and n is odd. The product of an odd and even number is an even product."
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: If x + y is odd for integers x and y, then x * y is even?

    Quote Originally Posted by lamentofking View Post
    So could I say, "if the sum is odd, then either m is odd and n is even or m is even and n is odd. The product of an odd and even number is an even product."
    You can say it, and that's what the statement means in terms of 'words', but it still doesn't constitute as proof. Look at what I said in my last post.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    69
    Thanks
    1

    Re: If x + y is odd for integers x and y, then x * y is even?

    The 3 line equal sign means "defined as"? Well then I can say that x + y is odd because either x is odd and y is even or x is even and y is odd. Their product is even because the product (mod) 2 will yield a remainder of 0.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: If x + y is odd for integers x and y, then x * y is even?

    x+y=2n+1 -> one is odd and one is even.
    evenxodd=even
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: If x + y is odd for integers x and y, then x * y is even?

    Quote Originally Posted by lamentofking View Post
    The 3 line equal sign means "defined as"?
    It means 'equivalent to' or in this case, 'congruent to'.

    Well then I can say that x + y is odd because either x is odd and y is even or x is even and y is odd.
    Tbh, I'm not sure how rigorously this question wants you to prove your statement as to whether you can assume odd + even = odd for all integers. I personally would check each case:

    a) x, y = even
    b) x, y = odd
    c) x = odd, y = even OR y = odd, x = even.

    Do this by writing them in the aforementioned form i.e. say for the first case a) if x, y = even, then we can write x = 2n, \ y = 2m for some  n, m \ \in \mathbb{Z^{+}}

    Now obviously x + y = 2n + 2m = 2(n + m) and as n, \ m \ \in \mathbb{Z^{+}} then x + y is in the form 2k, \ k \in \mathbb{Z^{+}} hence is even, so that eliminates this case.

    Their product is even because the product (mod) 2 will yield a remainder of 0.
    You will need to prove this the way I have above - once you've checked each case and confirmed that only case c) holds for the statement, write x = 2n, \ y = 2m - 1 or vice versa for some n, m \ \in \mathbb{Z^{+}} and multiply them together and the results falls out fairly quickly.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: If x + y is odd for integers x and y, then x * y is even?

    Reply to post #7. Why so complicated and obtuse?
    What's wrong with post #6?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: If x + y is odd for integers x and y, then x * y is even?

    Quote Originally Posted by Hartlw View Post
    Reply to post #7. Why so complicated and obtuse?
    What's wrong with post #6?
    Tbh, I have no idea what level of rigour OP needs in his proof of the statement so better safe than sorry, I suppose. There's nothing wrong with post #6 but it assumes odd + even = odd and odd x even = even and I have no idea whether OP can assume that or not, hence the long post. But I dunno.

    Edit: I wasn't trying to undermine your post or anything, if that's what you mean. I was in the process of typing my post out when you posted your's.
    Last edited by FelixFelicis28; September 5th 2013 at 06:12 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: If x + y is odd for integers x and y, then x * y is even?

    Nothing is assumed.
    x+y = odd is given. -> x+y=2n+1 -> x and y can't both be even or odd.
    oddxeven=(2n+1)(2m)=even. Sorry, thought that was obvious.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: If x + y is odd for integers x and y, then x * y is even?

    Quote Originally Posted by Hartlw View Post
    Nothing is assumed.
    x+y = odd is given. -> x+y=2n+1 -> x and y can't both be even or odd.
    Tbh, I agree, this part may have been a bit OTT but as I've said, I have no idea what OP can assume or not so wrote it out on my post.

    oddxeven=(2n+1)(2m)=even. Sorry, thought that was obvious.
    Regardless of how obvious it is, it doesn't constitute as proof, especially if the question asks you to prove even x odd = even (which is what I interpreted what the question was getting at, anyway). Apologies if that isn't the case.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: If x + y is odd for integers x and y, then x * y is even?

    "oddxeven=even is obvious" is not a proof. oddxeven=(2n+1)x(2m)=even is.

    But anyhow, my apologies. I get cranky when I see congruences because I don't understand them (I do understand the formal definition).

    If we are dealing with a set of objects for which congruence is defined,
    1) What is the definition that determines members of the set.
    2) What are the members of the set?
    3) If a and b belong to the set, what is the definition of axb and a+b.

    Or they are a relation. Is multiplication and division defined for a relation (subset definition). If so, what is the definition of multiplication and division for congruences as a relation?

    If my questions are too obtuse, you can just say so. Can't be more precise because I don't understand congruences.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,963
    Thanks
    1631

    Re: If x + y is odd for integers x and y, then x * y is even?

    Yes, if m+ n is odd then one of m or n is even, the other odd. Whether then saying that "therefore mn is even" is a good proof or not depends upon whether or not you have previously proved, and can use, the statements "if m+ n is odd then one is even, the other odd" and "if an integer is even, then its product with any other integer is even".

    If not, a complete proof of "if m+ n is odd then mn is even" would have to include proofs of those.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: If x + y is odd for integers x and y, then x * y is even?

    Quote Originally Posted by HallsofIvy View Post
    Yes, if m+ n is odd then one of m or n is even, the other odd. Whether then saying that "therefore mn is even" is a good proof or not depends upon whether or not you have previously proved, and can use, the statements "if m+ n is odd then one is even, the other odd" and "if an integer is even, then its product with any other integer is even".

    If not, a complete proof of "if m+ n is odd then mn is even" would have to include proofs of those.
    That's exactly what I did:
    x+y = odd is given. -> x+y=2n+1 -> x and y can't both be even or odd.
    oddxeven=(2n+1)(2m)=even. Sorry, thought that was obvious.

    Do you have a problem with "x+y=2n+1 -> x and y can't both be even or odd."

    OK, I'll spell it out: if x and y are odd: x=2n+1, y=2m+1 -> x+y=2(m+n) + 2 = even
    If x and y are even, x=2n, y=2m, x+y=2(m+n) = even. But x+y is given as odd. So x and y can't both be even or odd.

    I'm really confused by all these responses to a very simple question and answer.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: If x + y is odd for integers x and y, then x * y is even?

    An instructor would probably want a proof such as this:

    Suppose x + y = 2m + 1 (given).

    Case 1: x = 2k (x is even)

    Then y = 2m + 1 - 2k = 2(m-k) + 1, that is, if x is even, y is odd.

    Case 2: x = 2k + 1 (x is odd)

    Then y = 2m + 1 - (2k + 1) = 2(m - k ) + 1 - 1 = 2(m - k), that is, y is even.

    Thus in either case, we have one odd integer, and one even integer.

    So without loss of generality we may take x = 2k, y = 2m + 1 (or else consider y + x).

    Then: xy = (2k)(2m + 1) = 4km + 2k = 2(2km + k), that is: xy is even.

    The "completeness" of this proof lies in the fact that an integer (x in this case) must be either even or odd (and not both), something which might be considered obvious (but perhaps not).

    An alternative proof (based on divisibility):

    If x is even, then 2|x, so 2|xy thus xy is even (since if x = 2k, then xy = (2k)y = 2(ky)) (no matter whether y is even OR odd). It follows from 2 does not divide x+y, and 2 does not divide y that 2 does not divide y:

    for if 2|x, 2|y, then x+y = 2x + 2y = 2(x+y), so that 2|x+y, contradicting the given that x+y is odd.

    If x is odd, then given that 2 does not divide x + y, we must have x + y = 2n + 1 (0 and 1 are the only possible remainders upon division by 2, and thus x = 2k + 1), and it follows that 2|y:

    for if 2 does not divide y, then x = 2k + 1, y = 2m + 1 and x + y = 2k + 2m + 2 = 2(k + m + 1), which clearly is divisible by 2, a contradiction.

    So if x is odd, 2|y, whereupon 2|xy since xy = x(2t) = 2(xt).

    Now, while both of these are apparently long-winded explications of an apparently intuitively obvious fact, their approach generalizes very well to the more general setting of a unique factorization domain (ring) (such a polynomials) where we no longer have such a clear intuitve idea of what the individual elements look like.

    Proofs differ in their level of rigor, for some, it's a stylistic affair. None of the proofs given (including mine) qualify as a "formal" proof, but rather are "semi-formal" designed to CONVINCE. For example, when Hartlw says:

    "If x+y is odd, x and y can't both be even or odd"

    A person seeing such a statement may ask: "well, WHY?"

    His answer:

    "OK, I'll spell it out: if x and y are odd: x=2n+1, y=2m+1 -> x+y=2(m+n) + 2 = even
    If x and y are even, x=2n, y=2m, x+y=2(m+n) = even. But x+y is given as odd. So x and y can't both be even or odd"

    is in spirit the same argument by contradiction as I give in my 2nd proof. If someone were to question this further, by asking:

    "Why must an integer be either even or odd? Why can't it be BOTH, or nether?",

    a deeper investigation into the defining structure of the integers would be required (one might proceed by examining differences of integers, and absolute values, and conclude that since a - b is an integer, if we wish for |a - b| to be a positive integer, we must have: |a - b| ≥ 1...that is, 1 is the *smallest* positive integer, and thus the smallest distance between integers. Or, one might use the inductive nature of positive integers to conclude any difference between integers is a sum of 1's. Or one might use the theory of equivalence relations to show that x~y <=> x - y = 2k defines an equivalence relation on the integers, and conclude that this partitions the integers into 2 disjoint sets). My point being, under almost ANY proof, lies still another proof, until one gets to the "bottom axioms" of set theory and propositional logic, which are taken on faith because they prove the things we expect to be true (what is provably true conforms to what we intuitively FEEL to be true).

    Here, we must pause, and reflect a bit on what we actually accomplish when undertaking a proof, and what we feel the nature of truth is. Mathematical truth is, to a large degree, a matter of consensual agreement of certain things, one of which is that integers (appropriately defined) are either even, or odd, but not both, and this clean division of integers is felt to be clear enough on its own to be called "obvious".
    Thanks from FelixFelicis28
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 5th 2011, 11:47 PM
  2. Replies: 7
    Last Post: August 3rd 2010, 01:31 PM
  3. Matrix of integers whose inverse is full of integers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 02:02 PM
  4. Replies: 4
    Last Post: February 24th 2008, 03:08 PM
  5. Replies: 2
    Last Post: October 14th 2007, 03:18 PM

Search Tags


/mathhelpforum @mathhelpforum