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

Show that the number of reduced residues $$a \bmod 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)?

• is this right? - 'By the generalized Euler criterion, $x^m−1≡1modp^α$ '. Shouldn't it be $x^m≡1modp^α$ or $x^m−1≡0modp^α$ ?
– JMP
Commented May 23, 2015 at 8:21
• Please, do not use \displaystyle in the title. See here for more information. Commented May 24, 2015 at 9:56
• This is Theorem $1$ in R. Baillie & S.S. Wagstaff, Jr. Lucas Pseudoprimes, Mathematics of Computation Vol. 35, No. 152 (Oct., 1980), pp. 1391-1417. Chase links to that for further related work. Commented Feb 25 at 23:34

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