How to Find a Quadratic Nonresidue Modulo a Prime p

Title: How to Find a Quadratic Nonresidue Modulo a Prime p Category: mathematics

A quadratic nonresidue modulo an odd prime $p$ is a number that is not congruent to the square of any integer modulo $p$. When $p \equiv 1 \pmod 4$, there is no single candidate that works for every prime, but Euler’s criterion gives a direct test. Try candidates and stop as soon as the test identifies one.

Test candidates with Euler’s criterion

For any integer $a$ not divisible by $p$, Euler’s criterion states

$$a^{(p-1)/2} \equiv \begin{cases} 1 \pmod p & \text{if }a\text{ is a quadratic residue modulo }p,\\ -1 \pmod p & \text{if }a\text{ is a quadratic nonresidue modulo }p. \end{cases}$$

Since $-1 \pmod p$ is represented by $p-1$, you can test a candidate by computing the modular power $a^{(p-1)/2} \bmod p$. If the result is $p-1$, then $a$ is a nonresidue. If it is $1$, $a$ is a residue, so try another value.

Use modular exponentiation rather than calculating the full, potentially enormous integer power. Standard repeated-squaring methods compute the remainder efficiently.

A guaranteed search procedure

Start with $a=2$ and test consecutive integers up to $p-1$, skipping any multiple of $p$. The search is guaranteed to find a nonresidue: among the $p-1$ nonzero residue classes modulo $p$, exactly $(p-1)/2$ are squares and $(p-1)/2$ are nonsquares. In particular, a nonresidue exists among the candidates from $2$ through $p-1$.

In pseudocode:

for a = 2, 3, ..., p - 1:
    r = a^((p - 1)/2) mod p
    if r = p - 1:
        return a

The exponentiation and remainder are taken modulo $p$. The loop will not reach a multiple of $p$ before it finds an answer, since all the tested values are less than $p$.

Worked example: p = 17

Here $(p-1)/2=8$. Test $a=2$ first:

$$2^8 = 256 \equiv 1 \pmod{17}.$$

So 2 is a quadratic residue, not the answer. Next test $a=3$:

$$3^2 \equiv 9,\qquad 3^4 \equiv 13,\qquad 3^8 \equiv 13^2 = 169 \equiv 16 \pmod{17}.$$

Because $16 \equiv -1 \pmod{17}$, Euler’s criterion shows that 3 is a quadratic nonresidue modulo 17.

Why the condition p ≡ 1 mod 4 is not enough

The congruence $p \equiv 1 \pmod 4$ tells you that $-1$ is a square modulo $p$. It does not determine whether 2, 3, or any other fixed small number is a nonresidue. For example, 2 is a nonresidue when $p \equiv 5 \pmod 8$, but it is a residue when $p \equiv 1 \pmod 8$.

A small shortcut sometimes helps. If $p \equiv 5 \pmod 8$, then 2 is a nonresidue by the supplementary law for 2. If $p \equiv 1 \pmod 8$, test another candidate with Euler’s criterion. For an odd prime $p \ne 3$ with $p \equiv 1 \pmod 4$, quadratic reciprocity also gives $(3/p)=(p/3)$: thus 3 is a nonresidue when $p \equiv 2 \pmod 3$, and a residue when $p \equiv 1 \pmod 3$.

These shortcuts can save tests, but the Euler-criterion search works in every case. For instance, with $p=13$, 2 is a residue because $2^6 \equiv 1 \pmod{13}$, and 3 is a residue because $3^6 \equiv 1 \pmod{13}$. Testing 5 gives $5^2 \equiv -1 \pmod{13}$, so $5^6 \equiv (-1)^3 \equiv -1 \pmod{13}$; therefore 5 is a nonresidue.

Common mistakes

• Assuming 2 always works. Whether 2 is a residue depends on $p$ modulo 8.
• Calling a number a nonresidue because it is not visibly a square as an integer. The question is whether it is congruent to a square modulo $p$; Euler’s criterion checks that precisely.
• Using a candidate divisible by $p$. Euler’s criterion in this form applies only when $p$ does not divide $a$; a multiple of $p$ is congruent to zero and is not a nonzero quadratic residue or nonresidue.
• Treating $p \equiv 1 \pmod 4$ as a formula for the answer. It guarantees that $-1$ is a residue, but finding another nonresidue requires testing or using additional information about $p$.