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... [closed]

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 even or exactly half of its elements are even. (Gallian, Contemporary Abstract Algebra, Exercise 24, Chapter 3.)

Solution 1:

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.

Solution 2:

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.