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.
 A: 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.
A: 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.
A: 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.
