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 '15 at 8:21
  • $\begingroup$ Please, do not use \displaystyle in the title. See here for more information. $\endgroup$ – Martin Sleziak May 24 '15 at 9:56

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

| cite | improve this answer | |
  • $\begingroup$ Excellent answer, thank you $\endgroup$ – St Vincent May 24 '15 at 17:53
  • $\begingroup$ @StVincent Thank you! $\endgroup$ – Alex W May 24 '15 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.