I am trying to understand a proof (from a book) that there are at most $(n-1)/4$ non-wittnesses against the primality of $n$ in the Miller-Rabin algorithm that are coprime to $n$.
We set the prime factorisation of $n$ to $n = \prod_{p | n} p^{e(p)}$.
In one passage the author considers the following two subgroups of $\mathbb{Z}_n^{\times}$
$K = \{ a + n\mathbb{Z} : gcd(a,n) = 1 \text{ and } a^{n-1} \equiv \pm 1 \text{ mod } p^{e(p)} \text{ for all primes $p$ such that } p | n\}$
$M = \{ a + n\mathbb{Z} : gcd(a,n) = 1 \text{ and } a^{m} \equiv 1 \text{ mod } n\}$.
He observes that $M \le K$ which is clear. Then he says that the index $(K : M)$ is a power of $2$ since the square of each element of $K$ is an element in $M$. I can not follow this argumentation, could you please explain that to me?
Let $G$ be a finite Abelian group, written multiplicatively, and $H$ a subgroup. If $a^2\in H$ for all $a\in G$, then $\overline a^2$ is the identity element in the quotient group $G/H$ (where $\overline a$ is the image of $a\in G/H$). The order of $\overline a$ in $G/H$ is either $1$ or $2$.
If the order of $G/H$ is not a power of two, it has an odd prime factor $p$. By Cauchy's theorem, $G/H$ would then have an element of order $p$; this gives a contradiction.