{"id":793,"date":"2020-12-12T13:22:20","date_gmt":"2020-12-12T13:22:20","guid":{"rendered":"https:\/\/integralsandseries.in\/?p=793"},"modified":"2025-11-10T06:10:03","modified_gmt":"2025-11-10T06:10:03","slug":"the-group-of-units-in-the-integers-modulo-n","status":"publish","type":"post","link":"https:\/\/integralsandseries.in\/?p=793","title":{"rendered":"When is the group of units in the integers modulo n cyclic?"},"content":{"rendered":"\n

\nIt is easy to see with the help of Bezout’s identity<\/a> that the integers co-prime to $n$ from the set $\\{0,1,\\cdots, n-1\\}$ form a group under multiplication modulo $n$. This group is denoted by $(\\mathbb{Z}\/n\\mathbb{Z})^*$ and it’s order is given by the Euler’s Totient function<\/a>: $\\varphi(n) = |(\\mathbb{Z}\/p\\mathbb{Z})^*| $. Gauss showed that $(\\mathbb{Z}\/n\\mathbb{Z})^*$ is a cyclic group if and only if $n=1,2,4,p,p^k$ or $2p^k$, where $p$ is an odd prime and $k > 0$. It is very easy to verify this for $n=1,2$ and $4$, as one can simply list out all positive integers less than and co-prime to $n$. So, we will only focus on proving that $(\\mathbb{Z}\/n\\mathbb{Z})^*$ is cyclic for the remaining three cases.\n<\/p>\n\n\n\n\n

\nTheorem 1: <\/b> $(\\mathbb{Z}\/p\\mathbb{Z})^*$ is cyclic if $p$ is a prime.\n<\/p>\n\n

Proof: <\/b> Let $d_1, d_2, \\cdots , d_r$ be all the possible orders of the elements of $(\\mathbb{Z}\/p\\mathbb{Z})^*$. Let $e=\\text{lcm}(d_1, d_2, \\cdots, d_r)$ and factor $e=p_1^{a_1} p_2^{a_2}\\cdots p_k^{a_k}$ as a product of distinct prime powers. By the definition of $\\text{lcm}$, for each $p_i^{a_i}$ there is some $d_j$ divisible by it. Since the $d_j$’s are orders of elements of $(\\mathbb{Z}\/p\\mathbb{Z})^*$, there is an element $x_i$ whose order is $p_i^{a_i} t$. Then, the element $y_i = x_i^t$ has order $p_i^{a_i}$. Hence, $y_1 y_2\\cdots y_k$ has order $e$. Thus, we have found an element of order $e$. Therefore, $e|p-1$. But the polynomial $x^e-1$ has $p-1$ roots $(\\text{mod }p)$. Since $\\mathbb{Z}\/p\\mathbb{Z}$ is a field, any polynomial of degree $e$ cannot have more than $e$ roots. Therefore, $p-1\\leq e$ and we deduce that $e=p-1$. Thus, we have found an element of order $p-1$. <\/p>\n\n\n\n\n

Theorem 2: <\/b> $(\\mathbb{Z}\/p^a \\mathbb{Z})^*$ is cyclic for any $a\\geq 1$ if $p$ is an odd prime.<\/p>\n

\nProof:<\/b> For $a=1$, we are done by Theorem 1. Let $g$ be a primitive root $(\\text{mod }p)$. We first find a $t$ such that $(g+pt)^{p-1}\\not\\equiv 1 \\; (\\text{mod }p^2)$. If $g^{p-1}\\not\\equiv 1 \\; (\\text{mod }p^2)$, then we can take $t=0$. Otherwise, we can choose $t=1$. Indeed, we have $(g+p)^{p-1}\\equiv 1+p(p-1) g^{p-2} \\not \\equiv 1 \\; (\\text{mod }p^2)$. Let $g+pt$ have order $d\\; (\\text{mod }p^a)$. Then, $d|p^{a-1} (p-1)$. Since $g$ is a primitive root modulo $p$, $(p-1) | d$. So, $d=p^{r-1} (p-1)$ for some $r\\leq a$. We also know that $(g+pt)^{p-1} = 1+p s$ where $s \\nmid p$. Thus,\n$$\n\\begin{aligned}\n(g+pt)^{p(p-1)} &= (1+ps)^{p} \\\\\n&= \\sum_{i=0}^{p} \\binom{p}{i} (ps)^i \\\\\n&\\equiv 1+p^2 s \\; (\\text{mod }p^3)\n\\end{aligned}\n$$\nBy induction, it follows that\n$$ (g+pt)^{p^{b-1}(p-1)} \\equiv 1+p^b s \\; (\\text{mod }p^{b+1}) $$\nNow, $g+pt$ has order $d=p^{r-1}(p-1)\\; (\\text{mod } p^a)$ which implies $(g+pt)^{p^{r-1}(p-1)} \\equiv 1 \\; (\\text{mod }p^a)$. But then $1+p^r s \\equiv 1 \\; (\\text{mod } p^{r+1})$ if $r\\leq a-1$, which implies $p | s$, a contradiction. Thus, $r=a$.\n<\/p>\n\n\n\n

\nTheorem 3:<\/b> $(\\mathbb{Z}\/2p^a \\mathbb{Z})^*$ is cyclic for any $a\\geq 1$ if $p$ is an odd prime.\n<\/p>\n

\nProof:<\/b> This follows immediately from Theorem 2 and the Chinese remainder theorem<\/a>.\n<\/p>\n\n\n\n\n

\nThe fact that $(\\mathbb{Z}\/n\\mathbb{Z})^*$ can be cyclic only for the cases discussed above can also be verified easily using the Chinese remainder theorem.\n<\/p>\n\n\n\n

References<\/h2>\n