Suppose $n$ is an even positive integer and $H$ is a subgroup of $\mathbb Z/n \mathbb Z$. Prove that either every element of $H$ is...

This proof uses very elementary group theory (as per Gathdi's request) — it does not use homomorphisms or cosets, and it does not even assume the well-known result that every subgroup of a cyclic group is cyclic (a special case of it is proved here itself).

$\mathbb Z / n \mathbb Z = \{0, 1, \ldots, n - 1\}$.

Let $H$ be any subgroup of $\mathbb Z / n \mathbb Z$. If all elements of $H$ are even, we have the desired result. Otherwise, if at least one element of $H$ is odd, let $k$ be the least such odd element. Then we can prove that

  1. $H = \langle k \rangle$, the cyclic subgroup generated by $k$, and
  2. $H$ has even order, and half the elements of $H$ are even.

To prove the first statement, let $m$ be any element of $H$. Then using the division algorithm, \begin{equation*} m = qk + r, \quad 0 \le r < k \end{equation*} for some integers $q$ and $r$. Now, $r < k$ is an element of $H$ (since $r = m - qk$, $m, k \in H$), so it cannot be odd, due to our assumption on $k$. But if $r$ is even, then $k - r > 0$ is an odd element of $H$, which is possible only if $k - r \ge k$, so in fact, $k - r = k$ (since $r \ge 0$). Thus, $r = 0$, and $m = qk$, which proves that $H = \langle k \rangle$.

Now, the order of $H$ is the order of the element $k$, which is the smallest positive integer $s$ such that $sk = ln$, for some integer $l$ (as $n$ is the order of the group $G$). But given that $n$ is even, and $k$ is odd, it must be that $s$ is even. Thus, $H$ has even order, and since $H = \{0, k, 2k, 3k, \ldots, (s - 1)k \}$, exactly half of the elements of $H$, namely $0, 2k, 4k, \ldots, (s - 2)k$, are even.


Maybe try this: let $G=\mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}_n$. Then consider a subgroup $H$ of $G$. Because $G$ is cyclic, $H$ is cyclic. Suppose $H$ does not consist of all even elements. Then there exists an odd element in $H$. However, if $H$ is generated by an even element, then all elements in $H$ will be even. Therefore $H$ is generated by an odd element.

Now let's try to set up a bijection between even and odd elements of $H$. Let $H=\langle a\rangle$ where $a$ is odd. Then (in additive notation) $ca$ is even if $c$ is even, and odd if $c$ is odd.

Let $\phi(ca)=da$ where $d\equiv (c+1)\pmod a$, $0\leq d\lt |a|$. This clearly maps between even and odd components. You can check that this is a bijection fairly easily.

There could be a much easier way to do this, but this is what I came up with.


Since $n$ is even, one has $n\mathbf Z\subseteq 2\mathbf Z$ and, consequently, a morphism of quotient groups $$ f\colon \mathbf Z/n\mathbf Z\rightarrow \mathbf Z/2\mathbf Z. $$ Explicitly, $f$ maps de class of $m$ mod $n$ to the class of $m$ mod $2$, for any integer $m$. Of course, $f$ is surjective, and its kernel is the subgroup $2\mathbf Z/n\mathbf Z$ of ''even'' elements of $\mathbf Z/n\mathbf Z$.

Now, if $H$ is a subgroup of $\mathbf Z/n\mathbf Z$ then either $H$ is contained in the kernel of $f$, or it is not. In the former case, all elements of $H$ are even. In the latter case, the restriction of $f$ to $H$ is a surjective morphism $g$ from $H$ into $\mathbf Z/2\mathbf Z$. It follows that the kernel $\ker(g)$ of $g$ is a subgroup of $H$ of index $2$. In particular, $\ker(g)$ and its complement $H\setminus\ker(g)$ have the same number of elements since both are classes of the subgroup $\ker(g)$ of $H$. In particular, they have the same number of elements. The elements of $\ker(g)$ are the ''even'' elements of $H$, the elements of $H\setminus\ker(g)$ are the ''odd'' elements of $H$.