Problem F
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$,

\[ {\left(\frac{p}{q}\right)}{\left(\frac{q}{p}\right)}=(-1)^{(p-1)(q-1)/4} \]

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

\[ {\left(\frac{2}{p}\right)}=(-1)^{(p^2-1)/8} \]

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
3 7
144 3
5 7
9 7
7 7
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in