# Using Chinese Remainder Theorem

How would I solve the following set of modular equations where $p$ and $q$ are primes.

$N = p^3 (\mod q)$

$N = -q^3 (\mod p)$

If I know $N$, is it possible to solve and find $p$ and $q$ using Chinese Remainder Theorem? Chinese remainder theorem tell us how to solve this the other way around, but how can I solve it knowing N?

Not every $a$ in $\{0,1,\cdots,(q-1)\}$ is a cube mod $q$. If you know $N,$ there may be a way to find if it is a cube mod $q,$ however it's not as direct as e.g. quadratic reciprocity. A good possibility is to look up "cubic reciprocity" for which some facts are known.

Do the same for $N$ mod $p,$ and if say $N=e^3$ mod $p$ then $N=-(-e)^3$ mod $p.$ so it seems not much issue to "putting solutions together." '

• Wait... I'm confused how to apply cubic reciprocity here. If N were 2017, how would I go about solving this?
– user426764
Mar 18, 2017 at 19:38
• jacoby-- You would have to know $p,q$ the way you framed the question. For example there are primes $q$ for which 2017 is not congruent to a cube mod $q.$ Consider $q=13.$ All cubes are $0,1,5,8,12$ mod 13 but $2017=2$ mod 13. So no matter what the prime $p$ is in the first equation $N=p^3$ mod $13,$ that equation has no solution. Mar 18, 2017 at 20:03
• jacoby -- I still may not have your question right. You are given $N,$ and then wish to find any primes $p,q$ at all which make the two congruences hold? [If so can we allow $p=q$?] Mar 19, 2017 at 1:37
• @jacobyjones I await your clearing up the question in my last comment, since it seems it may be an interesting question. Mar 19, 2017 at 20:51
• sorry for the late response. Yes, I was wondering if there was a systematic way to find a list of p and q, which can be any primes (they can be equal) such that it satisfies that modulo statement when N is known.
– user426764
Mar 20, 2017 at 1:11