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 and an even number of the form .
You have to first prove that will be odd iff is odd and is even or is odd and is even. Then prove that their product must be even i.e. .
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.
It means 'equivalent to' or in this case, 'congruent to'.
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: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.
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 for some
Now obviously and as then is in the form hence is even, so that eliminates this case.
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 or vice versa for some and multiply them together and the results falls out fairly quickly.Their product is even because the product (mod) 2 will yield a remainder of 0.
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.
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.
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.oddxeven=(2n+1)(2m)=even. Sorry, thought that was obvious.
"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.
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.
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".