For $q, p$ odd primes such that $p \neq q$, there is not primitive root modulo $pq$.

Solution 1:

The argument below was used by Gauss to rule out primitive roots when in fact they don't exist.

Suppose that $g$ is a primitive root of $m \gt 2$. Then the congruence $x^2\equiv 1\pmod{m}$ has precisely $2$ solutions.

Now let $m=pq$ where $p$ and $q$ are distinct odd primes. By the Chinese Remainder Theorem, the congruence $x^2\equiv 1\pmod{pq}$ has $4$ solution. (Just combine in all possible ways the solutions mod $p$ and mod $q$.)

Added: Alternately, we show the stronger result that if $a\gt 2$ and $b\gt 2$ are relatively prime, then $ab$ does not have a primitive root. So we need to show there is no element of order $\varphi(ab)$ modulo $ab$. Suppose to the contrary that $g$ is such an element.

We have $\varphi(ab)=\varphi(a)\varphi(b)$. Both $\varphi(a)$ and $\varphi(b)$ are even. It follows that $\varphi(a)$ and $\varphi(b)$ each divide $m$, where $m=\frac{\varphi(a)\varphi(b)}{2}$.

From this we can see that $g^m\equiv 1\pmod{a}$, and $g^m\equiv 1\pmod{b}$, and hence $g^m \equiv 1\pmod{ab}$, contradicting the assumption that $g$ has order $\varphi(ab)$.

Solution 2:

Let $p, q$ be distinct odd primes. So $\gcd(p,q) = 1$. So by the structure theorem we have that $$ (\Bbb{Z}/pq\Bbb{Z})^{\times} \cong (\Bbb{Z}/p\Bbb{Z})^{\times} \oplus (\Bbb{Z}/q\Bbb{Z})^{\times} $$ which is not cyclic and hence contains no primitive roots.

Note that they are isomorphic as multiplicative groups.

EDIT: Seeing Bill's comments I guess it's worth mentioning that if $G_1, \ldots, G_n$ are finite groups then $ord((a_1,\ldots,a_n)) = lcm(ord(a_1),\ldots, ord(a_n))$, where each $a_i \in G_i$. So for any $(a,b) \in (\Bbb{Z}/p\Bbb{Z})^{\times} \oplus (\Bbb{Z}/q\Bbb{Z})^{\times}$, $ord((a,b)) = lcm(ord(a),ord(b)) = lcm(\varphi(p),\varphi(q))$ and so since $2 \mid \gcd(\varphi(p),\varphi(q))$, $lcm(\varphi(p),\varphi(q)) \neq (p-1)(q-1)$. So $(\Bbb{Z}/p\Bbb{Z})^{\times} \oplus (\Bbb{Z}/q\Bbb{Z})^{\times}$ is not cyclic.

Solution 3:

A primitive root modulo $pq$ would be an integer $a$ relatively prime to $pq$ such that (the resiude class of) $a$ generates the multiplicative group $(\mathbb{Z}/pq\mathbb{Z})^\times$, which has $\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$ elements. This is equivalent to requiring that the smallest positive $n$ such that $a^n\equiv 1\bmod pq$ is $n=(p-1)(q-1)$.

By the Chinese Remainder Theorem, $a^n\equiv 1\bmod pq$ if and only if $a^n\equiv 1\bmod p$ and $a^n\equiv 1\bmod q$. Can you show that there is an $n$ strictly smaller than $(p-1)(q-1)$ such that $a^n\equiv 1\bmod p$ and $a^n\equiv 1\bmod q$ for any $a$, thereby ruling out the existence of a primitive root? Hint: use Fermat's Little Theorem, and take a least common multiple.

Solution 4:

Well, the non-existence of a primitive root modulo $pq$ is exactly equivalent to the fact that the group of units of $\mathbb{Z}/pq \mathbb{Z}$ is not cyclic. But by the Chinese remainder theorem there is an integer $a$ such that $a \equiv 1$ (mod $q$) and $a \equiv -1$ (mod $p$), and there is an integer $b$ such that $b \equiv -1$ (mod $q$) and $b \equiv 1$ (mod $p$). Hence $a + pq\mathbb{Z}$ and $b + pq\mathbb{Z}$ are different elements of order $2$ in the group of units of $\mathbb{Z}/pq \mathbb{Z}$, so that group of units is not cyclic.