# Primitive roots and the Chinese remainder theorem

I'm going over some past papers and have been able to show that if $p$, $q$ are distinct odd primes and $\gcd (a, pq)=1$ then $a^{\operatorname{lcm}(p-1,q-1)} \equiv 1 \pmod {pq}$

the next part says taking $g$ to be a primitive root $\mod p$ and $h$ a primitive root $\pmod q$, apply the Chinese Remainder Theorem to specify an integer a whose order $\pmod {pq}$ is exactly $\operatorname{lcm}(p-1,q-1)$ but I'm not sure how to do this.

So far I've written out this but don't see how to solve

$$g^{p-1} \equiv 1 \pmod p$$

$$h^{q-1} \equiv 1 \pmod q$$

$$a^{\operatorname{lcm}(p-1,q-1)} \equiv 1 \pmod p$$

$$a^{\operatorname{lcm}(p-1,q-1)} \equiv 1 \pmod q$$

$$a=g^kh^l$$

-
Remember that the order of $a$ is $r$ if and only if $a^r \equiv 1$ and $a^{r/d} \not\equiv 1$ for proper divisors $d$ of $r$. – TMM Apr 28 '12 at 19:18
By the Chinese Remainder Theorem, there is an $e$ congruent to $g$ modulo $p$ and congruent to $h$ modulo $q$. – André Nicolas Apr 28 '12 at 19:35
OK so $e \equiv g$ mod p and $e \equiv h$ mod q but then $e=g \cdot m_1 +h \cdot m_2$ where $m_1$ and $m_2$ are inverses such that $qm_1 \equiv 1$ mod p and $pm_2 \equiv 1$ mod q and don't know how to find those? – Mike Davies Apr 28 '12 at 20:11
Unfortunately I used $e$ instead of the $a$ in your statement. Is your query about how to find $a$ which is simultaneously congruent to $g$ mod $p$ and to $h$ mod $q$? Or is your query about showing that this $a$ has the desired order mod $pq$? – André Nicolas Apr 28 '12 at 20:52
It asks how to specify such an $a$ and to show that a has the required order. – Mike Davies Apr 28 '12 at 21:18

Let $g$ be a primitive root modulo $p$, and $h$ a primitive root modulo $q$.
By the Chinese Remainder Theorem, there exists a unique integer $a$ modulo $pq$ such that $a\equiv g\pmod{p}$ and $a\equiv h\pmod{q}$.
(To "find" this $a$, since $p$ and $q$ are relatively there exist integers $x$ and $y$ such that $xp+yq = 1$. Then $xp\equiv 1\pmod{q}$, and $yq\equiv 1\pmod{p}$. Therefore, $a=gyq+hxp$ satisfies \begin{align*} a &= gyq+hxp \equiv gyq \equiv g(yq)\equiv g\pmod{p}\\ a &= gyq+hxp \equiv hxp \equiv h(xp) \equiv h\pmod{q} \end{align*} so $gyq+hxp\bmod pq$ will do.)
By the Chinese Remainder Theorem, \begin{align*} a^t\equiv 1\pmod{pq} &\iff a^t\equiv 1\pmod{p}\text{ and }a^t\equiv 1\pmod{q}\\ &\iff g^t\equiv 1\pmod{p} \text{ and }h^t\equiv 1\pmod{q}\\ &\iff t\equiv 0\pmod{p-1} \text{ and }t\equiv 0\pmod{q-1}\\ &\qquad\qquad\text{(since }g\text{ is a primitive root mod }p,\ h\text{ a primitive root mod }q)\\ &\iff p-1|t\text{ and }q-1|t\\ &\iff \mathrm{lcm}(p-1,q-1)|t. \end{align*} So the order of $a$ is exactly $\mathrm{lcm}(p-1,q-1)$.