# Prove directly, by contradiction, or contraposition? If the product of two integers is even, at least one of them must be even.

Hello I am having some trouble trying to know which way I should go as for this proof: ( we are suppose to use either direct, contradiction or contraposition)

Prove or disprove: If the product of two integers is even, at least one of them must be even. Im thinking the direct method of proof would work so heres my start: let a, b be PBAC even integers let a = 2m let b = 2n the product of 2m and 2n is 4mn 4mn= 2(2mn) because their both integers, their product must be an integer. Sense we multipling 2mn by 2 it is also even.

now lets have one of them be odd: let a be PBAC even integer let b be PBAC odd integer let a = 2m let b = 2n + 1 the product: 2m(2n +1) = 4mn + 2n = 2(2mn +1) m and n are integers so the product is an integer. adding 1 is also an integer but it is in the form of a multiple of 2, so it is even. so for a product to be even, and integer must be even QED? Is my proof correct? and how would i do this by contradiction/contraposition

Assume the product of two integers a and b are both even. Suppose not that integers a and b are odd a = (2m + 1) b = (2n + 1) let m and n be PBAC integers ab = (2m + 1)(2n + 1) ab = 4mn + 2m + 2n +1 ab = 2(2mn + m + n) + 1

Since (2mn + m + n) will be an integer by closure we can conclude that the product ab is an odd integer, which contradicts the assumption. This means at least one of the integers a or b must be even. QED?

Your proof isn't quite correct; you've concluded that if one of the integers is even, so is their product. You want to prove that it the product is even, then one of the integers was even.

The proof by contrapositive is the simplest, I think. The contrapositive simply says that

If neither integer is even, then the product is not even.

That is, the product of two odd integers is odd. This is easily verified from considering the equality

$$(2k + 1)(2m + 1) = 4km + 2k + 2m + 1 = 2(2km + k + m) + 1$$

• Even the direct proof isn't that bad. Start by taking a product of two integers $a,b$ that is even. I.e. $a \cdot b=2n$. Now think about factoring $2n$. You want to show that the 2 either goes into the $a$ factor or the $b$ factor. – mscook Nov 3 '13 at 18:24
• Actually, the direct proof requires a fact about prime numbers that the contrapositive proof does not. Of course, the fact is true, but it makes the proof significantly different. – Ryan Reich Nov 3 '13 at 18:26

Let the even integer $x$ be the product of the two integers $m$ and $n$.

$x=mn=2k$ $\quad k\in\mathbb{Z}$

Since $2|mn$ and $2$ is prime, either $2|m$ or $2|n$.

Here is the proof:

Suppose $p$ is a prime number and $p|ab$. Then either $p|a$ or $p|b$.

To prove this we will show that if $p$ does not divide $a$, then $p|b$. Suppose then that $p$ does not divide $a$. As the only positive integers dividing $p$ are $1$ and $p$, $\gcd(a,p)$ must be $1$ or $p$. It is not $p$ as $p$ does not divide $a$; hence $\gcd(a,p)=1$. Thus $a,p$ are coprime to each other and $p|ab$. It follows that $p|b$, as required.

Proof by contradiction: Assume the product of two integers $m$ and $n$ is even. Suppose not that both the integers are odd. That is $m=2r+1$ and $n=2s+1$ for some $r,s\in\mathbb{Z}$. But $mn=(2r+1)(2s+1)= 4rs+2r+2s+1=2(2rs+r+s)+1$ But since $2rs+r+s\in\mathbb{Z}$ we conclude that the product $mn$ is another odd integer which contradicts the assumption. Hence atleast one of the integers $m$ or $n$ must be even.