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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer May 6 '15 at 19:52
  • $\begingroup$ 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? $\endgroup$ – user2327195 May 6 '15 at 20:02
  • 2
    $\begingroup$ Find all quadratic nonresidues modulo $p$, and all modulo $q$, then combine per the Chinese remainder theorem. No royal way. $\endgroup$ – 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})$.


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.