Criteria for Primitive Roots Modulo N

When is the unit group $U_n$ cyclic (generated by a primitive root)?

For a positive integer $n$, the number of positive integers less than or equal to $n$ and co-prime to $n$ is called the totient function $\varphi(n)$. For example, $\varphi(6)=2$ and $\varphi(7)=6$. We will not prove properties of $\varphi(n)$ here. We just need to know that $\varphi(p^k)=p^{k-1}(p-1)$ for a prime $p$ and $\varphi(ab)=\varphi(a)\varphi(b)$ for co-prime $a,b$.

The set of positive integers less than or equal to $n$ and co-prime to $n$ forms a group under the operation: multiplication $\pmod n$. That is, for two elements $a$ and $b$, $a\bullet b=ab\pmod p$. Let's denote this by $U_n$. $$U_{15}=\{1,2,4,7,8,11,13,14\}$$ Be sure to check that $U_n$ really is a group under this operation!

We are interested in the question: For which $n$, $U_n$ has a generator? That is, it has an element $g$ so that $g^i\pmod n$ produces all elements of $U_n$. In other words, does there exist a $g\in U_n$ so that $\text{ord}(g)=\varphi(n)$? In fact, such a $g$ is called the primitive root of $n$. Now, we will find out which $n$ has a primitive root.

Let's check some values by hand. $n=2$ and $n=4$ works, and so does all primes $n=p$. What about $n=2^k$ for $k>2$?

We already know that, if $a$ is odd, then $8$ divides $a^2-1$. Then, by the identity: $$x^2-1=(x+1)(x-1)$$ we get that, $$x^{2^{k-1}}-1=(x^{2^{k-2}}+1)\cdots(x^2+1)(x^2-1)$$ On the right side, for odd $x$, $x^2-1$ is divisible by $8=2^3$ and each terms $x^{2^i}+1$ is divisibly by $2$. So for any odd $x$, $x^{2^{k-1}}-1$ is divisible by $2^k$. And this shows $n=2^k$ doesn't have any primitive root.

Let $n=ab$ where $a,b>2$ and $(a,b)=1$. Now, for any $g\in U_n$, $(g,a)=(g,b)=1$. Let the order of $a$ and $b$ modulo $g$ be $d$ and $e$. \begin{eqnarray*} g^d & \equiv & 1\pmod a\newline g^e & \equiv & 1\pmod b \end{eqnarray*} Now, we know that for any $n$ with $g^n\equiv1\pmod m$ and $\text{ord}_m(g)=d$, $d|n$. From Euler-Fermat's theorem,

$$g^{\varphi(a)} \equiv 1\pmod a$$ $$g^{\varphi(b)} \equiv 1\pmod b$$

Therefore, $d|\varphi(a),e|\varphi(b)$. On the other hand, $$g^{[\varphi(a),\varphi(b)]}\equiv1\pmod{ab}$$ where $[a,b]$ is the least common multiple of $a$ and $b$. Now, both $\varphi(a)$ and $\varphi(b)$ are even since $a,b>2$. Therefore,

\begin{eqnarray*} [\varphi(a),\varphi(b)] & \leq & \dfrac{\varphi(a)\varphi(b)}2\newline & = & \dfrac{\varphi(ab)}2\newline & = & \dfrac{\varphi(n)}2 \end{eqnarray*} This gives us that for such $n$, there is no $g$ for which $\text{ord}_n(g)=\varphi(n)$. So at least one of $a$ and $b$ must be less than or equal to $2$, and the other must be a prime power.

Summary The only $n$ for which $n$ has a primitive root are $2,4,p^k,2p^k$ for an odd prime $p$. And so, $U_n$ is cyclic for only those $n$.

Basic Definitions in Modular Arithmetic

Order

The order of $a$ mod $n$ is the smallest positive integer $p$ such that $a^p\equiv1$ mod $n$. The order of $a$ mod $n$ is usually written $ord_n(a)$.

An elementary but important result is that $ord_n(a)$ exists iff $gcd(a,n)=1$

Primitive Roots

$a$ is defined to be a primitive root of $n$ iff $ord_n(a)=\varphi(n)$, where $\varphi$ denotes Euler's Totient Function.

Quadratic Residues

$a$ is said to be a "quadratic residue" mod $n$ iff $\exists b$ s.t $b^2\equiv{a}$ mod $n$