In this situation, the fact that the product of two odd numbers is odd is not relevant. What is relevant is that the sum of two odd numbers is even. Let $\sigma$
and $\tau$
be odd permutations, then $\sigma$
and $\tau$
are both products of an odd number of transpositions, that is, $\sigma=t_{1}...t_{n}$
and $\tau=s_{1}...s_{m}$
where the $t_{i}$
and $s_{i}$
are transpositions and $n$
and $m$
are odd. We have $\sigma\tau=t_{1}...t_{n}s_{1}...s_{m}$
. Note that $\sigma\tau$
is a product of $n+m$
transpositions, and $n+m$ is even because $n$
and $m$
are odd. Therefore $\sigma\tau$
is an even permutation.
For a more general result:
Lemma. Let $G,H$ be finite groups. Then $\gcd(|G|, |H|)=1$ if and only if any subgroup of $G\times H$ is of the form $G'\times H'$ for some subgroups $G'\subseteq G$ and $H'\subseteq H$.
Proof.
"$\Rightarrow$" Let $K$ be a subgroup of $G\times H$. Let $e_G, e_H$ be neutral elements of $G, H$ respectively. Now let $(x,y)\in K$. Since $\gcd(|G|, |H|)=1$ then it follows that the order of $y$ and $y^{|G|}$ are the same. Thus $y^{|G|}$ generates $\langle y\rangle$. In particular we have
$$(x,y)\in K\ \Rightarrow$$
$$(x^{|G|}, y^{|G|})=(e_G, y^{|G|})\in K\ \Rightarrow$$
$$(e_G, y)\in K$$
The last implication because $y$ can be generated from $y^{|G|}$. Analogously if $(x,y)\in K$ then $(x, e_Y)\in K$.
Now if you consider projections
$$\pi_G:G\times H\to G$$
$$\pi_H:G\times H\to H$$
then you (obviously) always have
$$K\subseteq \pi_G(K)\times\pi_H(K)$$ What we've shown is the oppositie inclusion which completes the proof.
"$\Leftarrow$". Assume that $d=\gcd(|G|, |H|)\neq 1$. Let $p|d$ be a prime divisor and pick elements $x\in G, y\in H$ such that $|x|=|y|=p$ (they exist by the Cauchy's theorem). Now consider a subgroup $K$ of $G\times H$ generated by $(x, y)$. This subgroup is of prime order $p$. In particular if $K=G'\times H'$ then either $G'$ or $H'$ has to be trivial (because the order of product is equal to product of orders and $p$ is prime). But that is impossible since $(x,y)\in K$ and none of $x,y$ is trivial. Contradiction. $\Box$
So what it means is that if the orders of $G$ and $H$ are not relatively prime then there is a subgroup of $G\times H$ that is not a product of subgroups of $G$ and $H$. This should give you plenty of examples, e.g.
$$G=H=\mathbb{Z}_{n}$$
$$K=\langle(1,1)\rangle$$
Best Answer
One can embed $S_n$ can be embedded into$S_n\times S_n$ diagonally, i.e., $\sigma\mapsto (\sigma,\sigma)$ we see that $S_n$ embeds into $A_{2n}$ and so every finite group, order is odd or even, can be embedded into suitable alternating group.
(Compare it with similar statement any matrix group can be embedded into $SL(n)$ )