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)?

  • $\begingroup$ is this right? - 'By the generalized Euler criterion, $x^m−1≡1modp^α$ '. Shouldn't it be $x^m≡1modp^α$ or $x^m−1≡0modp^α$ ? $\endgroup$
    – JMP
    May 23, 2015 at 8:21
  • $\begingroup$ Please, do not use \displaystyle in the title. See here for more information. $\endgroup$ May 24, 2015 at 9:56

1 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$).

  • $\begingroup$ Excellent answer, thank you $\endgroup$
    – St Vincent
    May 24, 2015 at 17:53
  • $\begingroup$ @StVincent Thank you! $\endgroup$
    – Alex W
    May 24, 2015 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.