Euler's criterion does not yield -1 then p is composite) and the test becomes conclusive (bidirectional). The theorem may be restated:

: For all Proth numbers p, and for any quadratic nonresidue a of p, p is prime if and only if .

A quadratic nonresidue a of p may be identified when the Legendre symbol is -1, thus for such an a-value:

For such a value of a, the test is deterministic for both primality and compositeness; thus, for such an