0
$\begingroup$

I am looking at this problem and I am confused on how one could easily compute this. Is it just the intersection of either non-quadratic residue or quadratic residues of the respective p and q?

$\endgroup$
1
  • 2
    $\begingroup$ What is the question again? $\endgroup$
    – Jyrki Lahtonen
    Mar 26, 2012 at 19:51

3 Answers 3

Reset to default
1
$\begingroup$

Firstly the case $i=j=1$ is simple since the number $1$ will do this.

Secondly when $i = -1$ and $j=1$ we can use the number $-1$ since this is a QR mod $p'$ (prime) if and only if $p'\equiv 1$ mod $4$.

Thirdly when $i=j=-1$ we can use the number $2$ since this is a QR mod $p'$ if and only if $p\equiv 1,7$ mod $8$.

For the final case we may use $-2$ since we can see that the product of the $i,j$ values in the previous two cases match what we want (essentially we are using the homomorphism property of Legendre symbols here).

$\endgroup$
4
  • $\begingroup$ Hi fretty, why is mod 8 or mod 4 used or derived from? Thanks $\endgroup$
    – user27617
    Mar 26, 2012 at 15:09
  • $\begingroup$ These are the simple rules about when $-1$ or $2$ are QR's mod $p$ $\endgroup$
    – fretty
    Mar 26, 2012 at 18:09
  • 1
    $\begingroup$ Sorry. I have problems parsing this. What are the variables $i$ and $j$? Where did they come from? $\endgroup$
    – Jyrki Lahtonen
    Mar 26, 2012 at 19:50
  • $\begingroup$ The question seems to have been edited! $\endgroup$
    – fretty
    Mar 26, 2012 at 21:12
1
$\begingroup$

If you want to find $x$ such that it is a QR mod p and a NR mod q for example, you can just find a QR mod p (say m), find a NR mod q(say n), then use Chinese remainder theorem to solve

$$\begin{cases}x \equiv m & (\operatorname{mod} p) \\ x \equiv n & (\operatorname{mod} q) \end{cases}$$

$\endgroup$
2
  • $\begingroup$ Hi user27126, could you please provide an example for say i=1 and j=-1. I am not sure how the CR theorem can help here. Thank you. $\endgroup$
    – user27617
    Mar 26, 2012 at 13:59
  • $\begingroup$ Let's take $m = 0$, $n = 2$. You want to find x = 0 (mod 19), x = 2 (mod 37). Just use chinese remainder theorem to solve this congruence. $\endgroup$
    – user27126
    Mar 26, 2012 at 17:08
0
$\begingroup$

The solution by user27126 is fine, but you can cut a few corners. For example, there is one kind of number $n$ that is guaranteed to be a quadratic residue mod $p$ for all $p$ not dividing $n$ - do you know what I'm referring to? Also, you should know when $-1$ is a residue, that should settle another case without any need to resort to Chinese remainders. If you know when 2 is a residue, there goes another case. And so on.

$\endgroup$

You must log in to answer this question.