0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your statement in blue has nothing to the right of the $\equiv$ except for the (mod pq). Should there maybe be a 1 there, or some particular expression? $\endgroup$ – coffeemath Dec 17 '15 at 23:03
  • $\begingroup$ @coffeemath Yes, thanks, 1 was missing $\endgroup$ – GRS Dec 17 '15 at 23:04
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for this detailed solution. $\endgroup$ – GRS Dec 17 '15 at 23:58
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So it would be $q^{p-2} \times q + p^{q-2}\times p=q^{p-1}p^{q-1}$? and take this$ \mod pq$? $\endgroup$ – GRS Dec 17 '15 at 23:21
  • $\begingroup$ I only gave a way to get inverses, and did not check the Chinese remainder theorem approach to the problem. Maybe you could include the system of congruences you're solving, and the connection to inverses of $p,q$ mod $q,p$ to solving said system. $\endgroup$ – coffeemath Dec 17 '15 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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