# Proving That The Product Of Two Different Odd Integers Is Odd

Okay, here is how I begin my proof:

Let $q$ and $r$ be odd integers, then $q = 2k+1$ and $r = 2m+1$, where $k,m \in Z$.

$q \times r = (2k+1)(2m+1) \implies q \times r = 4mk + 2k + 2m + 1 \implies q \times r = 2(2mk + k + m) + 1$

I would then conclude that $q \times r$ results in an odd number, because 2 times an integer with one added to it is, by definition, an odd number.

However, how can I conclude this? Is $(2mk + k + m)$ in fact an integer? How do I know if the product of any two integers is an integer; similarly, does adding any two integers yield another integer? Now, obviously, I have an intuitive notion that these are true, but is there a way to prove them?

Side note: I would also appreciate it if someone could critique my proof.

-
Note that you haven't used the hypothesis that the integers are different anywhere in the proof; and indeed that hypothesis isn't required. –  joriki Mar 14 '13 at 17:40
You can just state that Z is closed under multiplication and addition. If you want to prove that, check out the proof for addition and multiplication here. –  Nik Bougalis Mar 14 '13 at 18:40
The question in the second paragraph, "how do I know that the product of any two integers is an integer?", should be promoted to the title. The side-note request to assess the proof has a trivial answer: CORRECT! –  zyx Mar 14 '13 at 18:40

Slightly more generally, note that multiplying $\rm\:m\, =\, k+an\:$ by any integer of the form $\rm\:1+bn\:$ doesn't change the remainder that $\rm\,m\,$ leaves when divided by $\rm\,n,\,$ i.e. the remainder stays = $\rm k,\,$ by

$$\rm (k+an)(1+bn)\, =\, k+n(a+b(k+an))$$

This is a special case $\rm\,j=1\,$ of $\rm\ mod\ n\!:\ \ \begin{eqnarray} x &\equiv&\,\rm k\\ \rm y &\equiv&\,\rm j\end{eqnarray}\ \Rightarrow\ xy\equiv\, k\, j,\ \$ the Congruence Product Rule

That $\rm\: a+b(k+an)\in \Bbb Z\:$ follows from the fact that $\rm\:a,b,c\in \Bbb Z\:\Rightarrow\: a + b\,c\in \Bbb Z,\:$ since integers are closed under multiplication, thus $\rm\:bc\in \Bbb Z,\:$ and also under addition, hence $\rm\:a + bc\in\Bbb Z.\:$ Finally, that $\rm\,\Bbb Z\,$ is closed under the operations of addition and multiplication follows from the recursive definitions of addition and multiplication in Peano arithmetic. Your proof is correct.

-

Your proof is fine, and it is true that the product of two integers is also an integer. You can't prove this, as this is one of the axioms of integers.

I recommend that you now prove this:

Let $p\in \mathbb{Z}$ and $p^2$ even. Then $p$ is even.

Note this isn't the same as saying $p$ even $\Longrightarrow$ $p^2$ even, which is also true.

-
What axioms of integers ? –  jca Mar 14 '13 at 17:45
You can't prove that the integers are closed under multiplication? That's fresh. –  Nik Bougalis Mar 14 '13 at 18:40
Yes I'm sorry, that was a mistake. I was using the set of "axioms" from a calculus book. Still, like Math Gems said, using the peano axioms, you can prove the closure. My point was integers are closed under addition and multiplication, so the OP didn't have to worry about that part being incorrect. Still, I should have been more careful. –  Orlando Mar 14 '13 at 18:45

A simple way of doing this is as follows. Let $p, q \in \mathbb{Z}$ be odd. Then suppose that $2 | pq$. Then, as $2$ is prime, we must have that $2 |p$ or $2 |q$.But either of these cases is impossible as both $p$ and $q$ are odd.

-
I think your proof assumes that if a prime number divides a product, it necessarily divides one of the factors. This is provable (via the Fundamental Theorem of Arithmetic), but you'd have to prove it. –  Malvolio Oct 27 '14 at 15:13
Of course it does. I assumed that the student knew this fact. Maybe that was a mistake. –  Chris Dugale Oct 28 '14 at 0:24
I was thinking that, but it strikes me as less obvious than the proposition you are trying to prove. (Apparently, this is exactly Euclid's lemma.) –  Malvolio Oct 28 '14 at 4:31
Really? To me it is more clear. Primes are defined with that algebraic property –  Chris Dugale Oct 28 '14 at 5:16
Obviousness is, I suppose, in the eye of the beholder. In fact, I proved Eulid's lemma (in my head) with the Fundamental Theorem, but later learned that the standard proof for the Fundamental Theorem depends on the lemma. A non-circular proof requires Bézout's identity, which I find unintuitive. –  Malvolio Oct 28 '14 at 6:53