2
$\begingroup$

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$

  • 0
    It asks how to specify such an $a$ and to show that$a$has the required order.2012-04-28

1 Answers 1

2

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