[email protected] #6 Math

Quadratic Residues

The great German mathematician C. F. Gauss studied the criteria for the equation

\[ x^2\equiv a \pmod{p} \]to have an integer solution $x$ for a prime $p$. For some tuples $a$ and $p$ there are several solutions, whereas others have none. For instance, $x^2\equiv 2 \pmod{7}$ has the solutions $3+7k$ and $4+7k$ for all integers $k$, but there are no solutions to $x^2\equiv 3 \pmod{7}$. The terminology “$a$ is a quadratic residue modulo $p$” is used to describe the case when there are solutions to the tuple $a$ and $p$. Identities for quadratic residues are often elegantly put in terms of the Legendre symbol

\[ {\left(\frac{a}{p}\right)}=\left\{ \begin{array}{rl} 0 & \mbox{If $p$ divides $a$.} \\ 1 & \mbox{If $p$ does not divide $a$ and $x^2\equiv a \pmod{p}$ has a solution.} \\ -1 & \mbox{Otherwise.}\end{array}\right. \]For positive integers $a,b$ and prime $p$, the following simple identity is known to hold

\[ {\left(\frac{a}{p}\right)}{\left(\frac{b}{p}\right)}={\left(\frac{ab}{p}\right)} \]Far more obscure is the identity proved by Gauss in 1801,
expressed as a conjecture by Euler in 1783, and succeeding two
erroneous proofs by Legendre (even mathematicians make mistakes
at times), called *the law of quadratic reciprocity*. It
says, that for distinct odd primes $p$ and $q$,

Expressions like the one above support the old mathematical
pun “the only odd prime is two”, since it is not generally true
when one of the primes is two. It turns out though, that there
is another simple relationship accounting for the case
$a=2$. Let $p$ be an odd prime (No, *not*
two!), then

Armed with these identities, you shouldn’t have any trouble answering whether a given quadratic equation has a solution or not, should you?

On the first line of input is a single positive integer $n$, telling the number of test scenarios to follow. Each test scenario is described as two positive integers $a$ and a prime $p$, both less than $2^{32}$ on a line of their own.

For each test scenario, output “yes” if there is at least one integer solution $x$ to $x^2\equiv a \pmod{p}$ for the given numbers $a$ and $p$, or “no” if there aren’t any.

Sample Input 1 | Sample Output 1 |
---|---|

5 3 7 144 3 5 7 9 7 7 7 |
no yes no yes yes |