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.
Best Answer
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.