$g$ is a primitive root mod $p$ and $h$ is a primitive root mod $q$. Using CRT find $k$ whose order is exactly lcm$(p-1,q-1)$

Question

Let $q$ and $p$ be unique primes. $g$ is a primitive root mod $p$ and $h$ is a primitive root mod $q$. Using CRT find $k$ whose order is exactly lcm$(p-1,q-1)$

I know that $g^{p-1} \equiv 1 \pmod p$ and $h^{q-1} \equiv 1 \pmod q$ since they are primitive roots.

I also know that $a^{lcm(p-1,q-1)}\equiv 1 \pmod {pq}$

CTR will require me to find the inverse of $q \pmod p$ and the inverse of $p \pmod q$ which I can't figure our how to do.

Answer 1

Since $p$ and $q$ are co-prime there exists $k$ satisfying $$k\equiv g\pmod p \land k\equiv h\pmod q \quad \text { by the CRT.}$$ Since $p\not |k \land q\not |k , $ and $p,\; q$ are prime, we have $k^m\equiv 1\pmod {pq}$ for some $m>0.$ $$\text {Let } n= ord (k) \text { modulo } p q.$$$$ \text {We have}\quad k^n\equiv 1\pmod p\implies g^n\equiv k^n\equiv 1\pmod p \land h^n\equiv k^n\equiv 1\pmod q)\implies$$ $$\implies ((p-1)\;|\;n \land (q-1)\;|\;n)\implies lcm (p-1,q-1)\;|\;n\implies lcm (p-1,q-1)\leq n.$$ $$\text {(1)........Therefore }\quad lcm (p-1,q-1)\leq n.$$ Now for brevity let $r=lcm (p-1,q-1).$ We have $$k^r\equiv 1\pmod p \land k^r\equiv 1\pmod q $$ so there are integers $A,B$ with $$(k^r= A p q+B p+1 )\land (0\leq B<q ).$$ $$\text {And} \quad q\;|\;(k^r-1)=q(A p)+B p\implies q\;|\;B p\implies q\;|\;B \implies B=0\implies$$ $$\implies k^r\equiv 1 \pmod {p q}.$$ By the def'n of $ n$, $$\text {(2)...therefore }\quad n\leq r=lcm (p-1,q-1).$$ From (1) and (2) we have $ lcm (p-1,q-1)=n= ord (k)$ modulo $p q$.

Answer 2

To get e.g. an inverse for $q$ mod $p$ you could use by Fermat's "Little Theorem" that $q^{p-1} \equiv 1$ (mod $p$). Then an inverse for $q$ would be $q^{p-2}$ since if that were multiplied by $q$ it would be $1$ from the Fermat statement just made. Of course this may be quite a large number...