# Find pseudo-square mod $n$

The definition of a pseudo-square in this case is let $n=pq$ where $p$ and $q$ are primes. A pseudo-square mod $n$ will be defined as a number $a$ such that $(\frac{a}{p}) = (\frac{a}{q}) = -1$ (Legendre symbol) so that $(\frac{a}{n}) = 1$ (Jacobi Symbol) although a is not congruent to a square mod $n$

So, the first question asks me to find all psuedosquares mod 15. So i can start out by writing 15 into its prime factorization, 5*3. So now i have
$(\frac{a}{3}) = (\frac{a}{5}) = -1$

It seems that the obvious way to do this would test everything mod 3 so test $(\frac{\{1,2\}}{3})$ The only number that will give me $-1$ in this case will be $(\frac{2}{3})$. Thus the only possible $a$ will be 2. So now I test $(\frac{2}{5})$ and see that gives me $-1$.
Now I test $(\frac{2}{15})$, well, $15\equiv 7$ mod 8 so $(\frac{2}{15}) = 1$
Thus $2$ is the only psuedosquare mod $15$

My main question is, imagine if I am given a larger number n, for example 187, which is factored 11*17. Is there a way to speed up this process without having to manually check every combination?
Also, how can I know for sure that $(\frac{2}{15}) = 1$ means 2 is not a square congruent to 15. I know that by definition of the jacobi symbol, $1$ does not imply that 2 is a square mod 15. But -1 does imply that its not. Do i manually have to check that 2 is not a square congruent to 15 somehow, or does the prereq that $(\frac{a}{3}) = (\frac{a}{5}) = -1$ automatically imply that its not.

• There's also $8$. $8 \equiv 2 \pmod{3}$ and $8 \equiv 3 \pmod{5}$, so $\bigl(\frac{8}{3}\bigr) = \bigl(\frac{8}{5}\bigr) = -1$. – Daniel Fischer May 6 '15 at 19:52
• Okay so is there a quick way to find these numbers larger than 2? Is there some system of equations that will give me all the numbers that work? – user2327195 May 6 '15 at 20:02
• Find all quadratic nonresidues modulo $p$, and all modulo $q$, then combine per the Chinese remainder theorem. No royal way. – Daniel Fischer May 6 '15 at 20:03

As pointed out by Daniel Fischer in his comment, determining which $a$ satisfies $(\frac{a}{p})=(\frac{a}{q})=-1$, only hard work will do the trick.

As to your other question, the interesting answer is that you don't have to check whether the resulting set of $a \mod pq$ are quadratic residues or not: they never are!

This follows easily from the fact that $(\frac{a}{p})=(\frac{a}{q})=-1$: suppose that $a$ is a quadratic residue $\mod pq$, then it follows that it also is a quadratic residue $\mod p$ and $\mod q$, which means that $(\frac{a}{p})=(\frac{a}{q})=+1$, a contradiction.

Also note that $(\frac{a}{pq})=+1$ is a corollary of $(\frac{a}{p})=(\frac{a}{q})=-1$, as $(\frac{a}{pq})$ equals $(\frac{a}{p})(\frac{a}{q})$.