Number of consecutive nonzero quadratic residues modulo an odd prime

ID: number-of-consecutive-nonzero-quadratic-residues-modulo-an-odd-prime

For an odd prime , the number of integers such that both and are quadratic residues modulo is
For example, modulo the quadratic residues are . The qualifying pairs are and , giving .
Write for the Legendre symbol. On the specified range neither input is zero, so the indicator of the required event is . Expand and sum. The complete Legendre-symbol sum gives
The quadratic Legendre-symbol correlation gives : extending to the full finite field only adds the zero terms at . Thus the count is . The first supplementary law for quadratic reciprocity identifies and completes the formula.

New to topics? Read the docs here!