2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Wait... I'm confused how to apply cubic reciprocity here. If N were 2017, how would I go about solving this? $\endgroup$
    – user426764
    Mar 18, 2017 at 19:38
  • $\begingroup$ 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. $\endgroup$
    – coffeemath
    Mar 18, 2017 at 20:03
  • $\begingroup$ 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$?] $\endgroup$
    – coffeemath
    Mar 19, 2017 at 1:37
  • $\begingroup$ @jacobyjones I await your clearing up the question in my last comment, since it seems it may be an interesting question. $\endgroup$
    – coffeemath
    Mar 19, 2017 at 20:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – user426764
    Mar 20, 2017 at 1:11

You must log in to answer this question.