Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
How do you propose to prove that it is not cyclic? –  Bill Dubuque Jun 23 '12 at 21:36
3  
I guess it's worth noting that the group isn't cyclic because $2 \mid (\phi(p),\phi(q))$. –  JSchlather Jun 23 '12 at 21:36
    
@Jacob I wondered what way Eugene had in mind. There are other ways too, e.g. see Geoff's answer. See also Product of two cyclic groups is cyclic iff their orders are co-prime. –  Bill Dubuque Jun 25 '12 at 17:01
add comment

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.

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

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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