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.
Well, it certainly depends on how you define things and how abstract you want to be but I guess I would come up with what I think is the easiest answer for me.
We define a relation on $\mathbb{Z}$: $a \equiv b \mod n \iff n \mid a-b$
If $a \equiv b \mod n$ then $\exists q \in \mathbb{Z}: nq = a-b$, but by the division algorithm we can write $b=nk+r$ such that $0 \leq r < n$. If we replace this instead of $b$ we'll have $a - (nk+r) = nq \implies a -r = nQ' \implies a \equiv r \mod n$
Therefore every integer number is congruent to some number $0\leq r<n$.
If $n=2$, then $r$ is either $0$ or $1$ provided that you take the standard order on integers for granted. However, it's easy to prove that there is no positive integer between $1$ and $0$. Because if there was an integer, say $m$, such that $0<m<1$, then the set $S=\{x \in \mathbb{Z}: 0<x<1\}$ would be a non-empty subset of natural numbers and hence it has a least element by the well-ordering principle. Let $m_0 = \min(S)$. But field axioms on reals implies that $0<m_0^2<m_0<1$, that means $m_0 ^2 < m_0 \in S$ and that's contradiction. But we have already assumed a well-defined order on integers (in fact on $\mathbb{R}$ and all of its subsets) which could be challenged depending on how you want to define an order on integers and how you build them. Hence, I have so far shown that there is no integer number between 1 and 0, I guess with shifting by $n$ one can prove that there is no integer number between $n$ and $n+1$. But anyway, the relation I have defined on $\mathbb{Z}$ can be proved to be an equivalence relation. Therefore, it partitions $\mathbb{Z}$ into disjoint non-empty subsets that are our equivalence classes. We call the equivalence class of $0$ as 'even' numbers and call the equivalence class $1$ as 'odd' numbers. Your statements now are obvious because our partitioned sets are disjoint (therefore a number can't be both even and odd) and their union is all of $\mathbb{Z}$ (any number must be either even or odd). This could be proved independently by using only the definitions of partitions and equivalence relations.
Now it's easily possible to prove that our partitioned set inherits a natural algebraic structure from $\mathbb{Z}$. I.e. $[a] + [b] = [a+b]$ and $[a].[b] = [a.b]$ where $[a]$ represents the class of all elements equivalent to $a$.
I guess it should be easy to prove by induction that if $s(n)$ is in the same equivalence class as $n$ then we'll have only equivalence class, therefore, to avoid that, $s(n)$ must fall in the other equivalence class because we have only two equivalence classes in $mod 2$.
I hope my arguments aren't that terrible and naive. I'm not a logician after all.
Best Answer
You have a good idea, but that's not quite the contrapositive. The contrapositive would be: "If $x$ and $y$ (integers) are not both odd, then $xy$ is also not odd." Another way of phrasing this would be "Let $x,y\in\Bbb{Z}$. If $x$ or $y$ is even, then $xy$ is even." I think you can finish it from here!