4
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jozef Jun 24 '12 at 6:00
  • $\begingroup$ Is that the Chinese theorem precisely? $\endgroup$ – Jozef Jun 24 '12 at 6:08
  • $\begingroup$ @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. $\endgroup$ – André Nicolas Jun 24 '12 at 6:51
  • $\begingroup$ But also $g^{\frac{\phi}{2}}$ is a solution to this congruence, so we conclude that it is congruence to -1 or 1? $\endgroup$ – Jozef Jun 24 '12 at 7:27
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.