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