Show that the number of reduced residues $a \mod m$ such that $a^{m-1} \equiv 1 \mod m$ is exactly $\prod_{p \mid m} \gcd(p-1,m-1).$

Question

Show that the number of reduced residues $a \mod m$ such that $a^{m-1} \equiv 1 \mod m$ is exactly $$\displaystyle \prod_{p \mid m} \gcd(p-1,m-1).$$

Suppose $f(x) = x^{m−1}−1$ and let $m = p^\alpha_1 \cdots p^\alpha_n$ denote the prime factorization of $m.$ If $p$ is prime, $p \mid m$ and $\alpha \geqslant 1,$ then $f(x)$ has $(m − 1, p − 1)$ roots modulo $p^{\alpha}.$ Thus $f(x)$ has $\displaystyle \prod (m − 1, p − 1)$ roots mod $m.$ Suppose $p \geqslant 3$ or $p = 2$ and $\alpha = 1$ or $2.$ By the generalized Euler criterion, $x^m−1 ≡ 1 \mod p^{\alpha}$ has $k = (m − 1, \phi(p^{\alpha})) = (m-1,p^{\alpha-1}(p-1))$ roots since $1^{\phi(p^{\alpha}/k)} \equiv 1 \mod p^{\alpha}.$ But $k = (m-1,p^{\alpha-1}(p-1)) =(m-1,p-1)$ since $p \mid m$ and hence $p \nmid m−1.$ We are left with the case that $p = 2$ and $\alpha \geqslant 3.$ Since $p = 2 \mid m$ we have that $m − 1$ is odd. Thus $x^{m−1} ≡ a \mod 2^{\alpha}$ has exactly $1$ solution. But in this case $1 = (m − 1, p − 1) = (m − 1, 2 − 1)$ as well. $ \Box$

Above is a elementary number theory proof. Question: How can this be proved using tools from abstract algebra (potentially group/ring theory)?

Answer 1

For $n\in\mathbb Z$ and group $G$ denote $r_n(G)=\{g\in G:g^n=1\}$. Obviously, if $G$ abelian group, then $r_n(G)\leq G$. Group of invertible elements of the ring $R$ denote $R^*$. We can say, that we are looking for $|r_{m-1}(\mathbb{Z}_m^*)|$. Denote $n=m-1$. By the chinese remainder theorem, $$ \mathbb{Z}_m^* \simeq \mathbb{Z}_{p_1^{\alpha_1}}^*\times\ldots\times \mathbb{Z}_{p_l^{\alpha_l}}^*, $$ where $p_i$ - distinct prime numbers, $\alpha_i\in\mathbb{Z}_{>0}$ and $m=p_1^{\alpha_1}\cdot\ldots\cdot p_l^{\alpha_l}$. It is clear, that $$ r_{n}(\mathbb{Z}_m^*)\simeq r_{n}(\mathbb{Z}_{p_1^{\alpha_1}}^*)\times\ldots\times r_{n}(\mathbb{Z}_{p_l^{\alpha_l}}^*), $$ hence $|r_{n}(\mathbb{Z}_m^*)|=\prod_{i=1}^l|r_{n}(\mathbb{Z}_{p_i^{\alpha_i}}^*)|$. In such a way, it remains to find $|r_{n}(\mathbb{Z}_{p_i^\alpha}^*)|$ for each $i$. If $p_i$ is odd, then $\mathbb{Z}_{p_i^{\alpha_i}}^*$ is cyclic of order $\varphi(p_i^{\alpha_i})$, hence $|r_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)|=\gcd(n,\varphi(p_i^{\alpha_i}))=\gcd(m-1,p_i-1)$. If $p_i=2$, then $\gcd(|\mathbb{Z}_{p_i^{\alpha_i}}^*|,n)=1$, therefore $r_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)$ must be $\{1\}$ and again $|r_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)|=\gcd(m-1,p_i-1)$. So $$ |r_n(\mathbb{Z}_m^*)|=\prod_{i=1}^l\gcd(p_i-1,m-1). $$

In essence, this argument is the same, as the proof of St Vincent. It can be generalized to any finite abelian group (and some rings other than $\mathbb Z$).