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

I'd really love your help with proving that for $q, p$ odd primes such that $p \neq q$, there is not primitive root modulo $pq$.

There's a theorem says that there's primitive root only for $2, 4, q^l, 2q^l$ for prime $q$ and $l \in {Z}$, but I guess I can't use it.

any other suggestions?

Thanks a lot

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

• Thank you very much, How do I know that for the system $x=1(\mod p),x=1(\mod q)$ and $x=a(\mod p),x=1(\mod q)$ and $x=b(\mod p),x=1(\mod q)$ and $x=a(\mod p),x=b(\mod q)$, where $a,b$ are both solutions for the $x^2=1 (\mod m)$ and $m$ is the prime, doesn't have two or more congruent solutions? – Jozef Jun 24 '12 at 6:00
• Is that the Chinese theorem precisely? – Jozef Jun 24 '12 at 6:08
• @Jozef: Mod $p$, the two solutions are congruent to $1$ and $-1$. Same for mod $q$. Chinese Remainder Theorem lets us produce something congruent to $1$ mod $p$ and congruent to $-1$ mod $q$, also the other way, as well as the usual congruent to $1$ mod both, or $-1$ mod both. – André Nicolas Jun 24 '12 at 6:51
• But also $g^{\frac{\phi}{2}}$ is a solution to this congruence, so we conclude that it is congruence to -1 or 1? – Jozef Jun 24 '12 at 7:27

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.

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.

• Regarding "take a LCM" in the final sentence, see this answer. – Bill Dubuque Jun 23 '12 at 21:43

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.