Exercise 2.8.25* (Number of solutions of the congruence $a^{m-1} \equiv 1 \pmod m$)

Proof.

a)

Write $m=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_l^{{\alpha }_l}$ the decomposition of $m$ in prime factors. Let $N$ be the number of reduced residues $a(\mathit{mod}m)$ such that $a^{m-1}\equiv 1(\mathit{mod}m)$. Then $N=\mathrm{Card}(A)$, where $$A=\{\alpha \in {(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}\mid {\alpha }^{m-1}=1\}.$$

( ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ is the group of invertible elements of $\mathbb{Z}∕\mathit{m\mathbb{Z}}$.)

Consider the sets

$$A_k=\{\gamma \in {(\mathbb{Z}∕p_k^{{\alpha }_k}\mathbb{Z})}^{\text{×}}\mid {\gamma }^{m-1}\equiv 1\},1\le k\le l.$$

Let $\phi$ be the map

$$\phi \{\begin{array}{ccc}\hfill A\hfill & \hfill \to \hfill & A_1\times A_2\times \cdots \times A_l\hfill \\ \hfill [a{\text{]}}_m\hfill & \hfill \mapsto \hfill & ([a{\text{]}}_{p_1^{{\alpha }_1}},[a{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[a{\text{]}}_{p_l^{{\alpha }_l}}).\hfill \end{array}$$

Then

• $\phi$ is well defined: if $a\equiv a^{\prime }(\mathit{mod}m)$, then $a\equiv a^{\prime }(\mathit{mod}{p}_k^{{\alpha }_k})$, because $p_k^{{\alpha }_k}\mid m$ for every index $k$. Thus $([a{\text{]}}_{p_1^{{\alpha }_1}},[a{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[a{\text{]}}_{p_l^{{\alpha }_l}})=([a^{\prime }{\text{]}}_{p_1^{{\alpha }_1}},[a^{\prime }{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[a^{\prime }{\text{]}}_{p_l^{{\alpha }_l}})$. Moreover, if ${[a]}_m\in A$, then ${[a]}_m^{m-1}=1$, therefore ${\left({[a]}_{p_k^{{\alpha }_k}}\right)}^{m-1}=1$ for every index $k$, because $p_k^{{\alpha }_k}\mid m$, and $m\mid a^{m-1}-1$. So $([a{\text{]}}_{p_1^{{\alpha }_1}},[a{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[a{\text{]}}_{p_l^{{\alpha }_l}})\in A_1\times A_2\times \cdots \times A_l$.
• $\phi$ is injective : if $\phi ({[a]}_m)=\phi ({[b]}_m)$, where $a,b\in \mathbb{Z}$, then $([a{\text{]}}_{p_1^{{\alpha }_1}},[a{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[a{\text{]}}_{p_l^{{\alpha }_l}})=([b{\text{]}}_{p_1^{{\alpha }_1}},[b{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[b{\text{]}}_{p_l^{{\alpha }_l}})$, thus $p_k^{{\alpha }^k}\mid b-a$ for every $k\in [[1,l]]$, therefore $m\mid b-a$, so ${[a]}_m={[b]}_m$.
• $\phi$ is surjective: if $([a_1{\text{]}}_{p_1^{{\alpha }_1}},[a_2{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[a_l{\text{]}}_{p_l^{{\alpha }_l}})$ is any element of $A_1\times A_2\times \cdots \times A_l$, by the Chinese Remainder Theorem, there exists $a\in \mathbb{Z}$ such that $a\equiv a_k(\mathit{mod}{p}^{{\alpha }_k})$ for every $k\in [[1,l]]$. Moreover, since $p^{{\alpha }^k}\mid a_k^{m-1}-1$, then $p^{{\alpha }^k}\mid a^{m-1}-1$ for every $k\in [[1,l]]$, therefore $m\mid a^{m-1}-1$, thus ${[a]}_m\in A$, and $\phi (a)=([a{\text{]}}_{p_1^{{\alpha }_1}},[a{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[a{\text{]}}_{p_l^{{\alpha }_l}})=([a_1{\text{]}}_{p_1^{{\alpha }_1}},[a_2{\text{]}}_{p_2^{{\alpha }_2}},\dots ,[a_l{\text{]}}_{p_l^{{\alpha }_l}})$. So $\phi$ is surjective.

This proves that $\phi$ is bijective, thus

$$\begin{array}{lll}\hfill |A|=|A_1\times A_2\times \cdots \times A_l|=|A_1|\cdot |A_2|\cdot \cdots \cdot |A_l|.& & \hfill \text{(1)}\end{array}$$

b)

Now we show that $|A_k|=(p_k-1)\wedge (m-1)$ for every $k$. To have shorter notations, write $p=p_k,\alpha ={\alpha }_k$. We compute $$\mathrm{Card}\{\gamma \in {(\mathbb{Z}∕p^{\alpha }\mathbb{Z})}^{\text{×}}\mid {\gamma }^{m-1}=1\},$$

where $p^{\alpha }\mid m,p^{\alpha +1}\nmid m$.

Consider first the case $p\ne 2$. Then ${(\mathbb{Z}∕p^{\alpha }\mathbb{Z})}^{\text{×}}$ has a generator $g$ by Theorem 2.39 and 2.40, of order $\varphi (p^{\alpha })=p^{\alpha -1}(p-1)$.

Let $\gamma$ be any element of ${(\mathbb{Z}∕p^{\alpha }\mathbb{Z})}^{\text{×}}$. Then $\gamma =g^k$ for some integer $k$ such that $0\le k<p^{\alpha -1}(p-1)$. Write $d=(p-1)\wedge (m-1)$ the gcd of $p-1$ and $m-1$. Then

$$\begin{array}{llll}\hfill {\gamma }^{m-1}=1& ⟺g^{k(m-1)}=1& \hfill & \\ \hfill & ⟺p^{\alpha -1}(p-1)\mid k(m-1)& \hfill & \\ \hfill & ⟺p^{\alpha -1}\frac{p-1}{d}\mid k\frac{m-1}{d}& \hfill & \\ \hfill & ⟺p^{\alpha -1}\frac{p-1}{d}\mid k,& \hfill & \end{array}$$

because $\frac{p-1}{d}\wedge \frac{m-1}{d}=1$, and $p^{\alpha -1}\wedge (m-1)=1$ (recall that $p\mid m$), thus $p^{\alpha -1}\wedge \frac{m-1}{d}=1$, and so

$$\left(p^{\alpha -1}\frac{p-1}{d}\right)\wedge \frac{m-1}{d}=1.$$

Since $0\le k<p^{\alpha -1}(p-1)$,

$$k\in K=\left\{0,p^{\alpha -1}\frac{p-1}{d},2p^{\alpha -1}\frac{p-1}{d},\dots ,(d-1)p^{\alpha -1}\frac{p-1}{d}\right\},$$

and two distinct values of $k\in K$ are not congruent modulo $\varphi (p^k)$, therefore the equation ${\gamma }^{m-1}=1$ has $d=(p-1)\wedge (m-1)$ solutions in ${(\mathbb{Z}∕p^{\alpha }\mathbb{Z})}^{\text{×}}$. This shows that

$$\mathrm{Card}\{\gamma \in {(\mathbb{Z}∕p^{\alpha }\mathbb{Z})}^{\text{×}}\mid {\gamma }^{m-1}=1\}=(p-1)\wedge (m-1),$$

for every odd prime divisor of $m$.

(Alternatively, we can use Corollary 2.32.)

Consider now the case $p=2$. We prove that the congruence $a^{2^{\alpha }-1}\equiv 1(\mathit{mod}{2}^{\alpha })$ has exactly one solution (this is also a consequence of Corollary 2.44).

By Theorem $2.43$ we can write

$$a\equiv {(-1)}^y{5}^z(\mathit{mod}{2}^{\alpha }),0\le y<2,0\le z<2^{\alpha -2}.$$

Then, using the part "unicity" of Theorem 2.43,

$$\begin{array}{llll}\hfill a^{2^{\alpha }-1}\equiv 1(\mathit{mod}{2}^{\alpha })& ⟺{(-1)}^{y(2^{\alpha }-1)}{5}^{z(2^{\alpha }-1)}\equiv 1(\mathit{mod}{2}^{\alpha })& \hfill & \\ \hfill & ⟺y(2^{\alpha }-1)\equiv 0(\mathit{mod}2),z(2^{\alpha }-1)\equiv 0(mod{2}^{\alpha -2})& \hfill & \\ \hfill & ⟺y\equiv 0(\mathit{mod}2),z\equiv 0(mod{2}^{\alpha -2})& \hfill & \\ \hfill & ⟺a\equiv 1(\mathit{mod}{2}^{\alpha }).& \hfill & \end{array}$$

Thus, for $p=2$, we have also

$$\mathrm{Card}\{\gamma \in {(\mathbb{Z}∕2^{\alpha }\mathbb{Z})}^{\text{×}}\mid {\gamma }^{m-1}=1\}=1=(p-1)\wedge (m-1)$$

c)

Therefore (1) shows that $$N=|A|=\underset{p\mid m}{\prod }[(p-1)\wedge (m-1)].$$

So the number of reduced residues $a(\mathit{mod}m)$ such that $a^{m-1}\equiv 1(\mathit{mod}m)$ is exactly $\underset{p\mid m}{\prod <!--\; FUNCTION\; APPLICATION\; -->}[(p-1)\wedge (m-1)]$.