A248222 Maximal gap between quadratic residues mod n.

1, 1, 2, 3, 3, 2, 3, 4, 3, 3, 4, 5, 5, 3, 5, 7, 4, 3, 5, 7, 6, 4, 5, 8, 3, 5, 3, 7, 4, 5, 5, 8, 6, 4, 5, 9, 5, 5, 6, 11, 6, 6, 6, 8, 6, 5, 5, 12, 4, 3, 6, 8, 7, 3, 8, 9, 7, 4, 6, 11, 7, 5, 9, 8, 9, 6, 7, 13, 7, 5, 7, 12, 5, 5, 7, 8, 11, 6, 7, 15, 3, 6, 8, 12, 13, 6, 11, 16, 7, 6

Offset: 1

Author

David W. Wilson and M. F. Hasler, Oct 04 2014

Keywords

• nonn

Comments

"Maximal gap between squares mod n" would be a less ambiguous definition.

The definition of quadratic residue modulo a nonprime varies from author to author. Sometimes, even when n is a prime, 0 is not counted as a quadratic residue. In this entry, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n.

See A248376 for the variant with the additional restriction that the residue be coprime to the modulus. - M. F. Hasler, Oct 08 2014

Examples

			For n=7, the quadratic residues are all numbers congruent to 0, 1, 2, or 4 (mod 7), so the largest gap of 3 occurs for example between 4 = 2^2 (mod 7) and 7 = 0^2 (mod 7).
For n=16, the quadratic residues are the numbers congruent to 0, 1, 4 or 9 (mod 16), so the largest gap occurs between, e.g., 9 = 3^2 (mod 16) and 16 = 0^2 (mod 16).
		

References

• K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 45.
• G. B. Mathews, Theory of Numbers, 2nd edition. Chelsea, NY, p. 32. [Does not require gcd(q,n)=1.]
• Ivan Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers, New York: John Wiley, 2nd ed., 1966, p. 69. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
• J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 270. [Does not require gcd(q,n)=1.]

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Quadratic Residue
• Wikipedia, Quadratic residue

Crossrefs

Cf. A063987, A130290, A088190, A088191, A088192.

Programs

PARI

(DD(v)=vecextract(v,"^1")-vecextract(v,"^-1")); a(n)=vecmax(DD(select(f->issquare(Mod(f,n)),vector(n*2,i,i))))

Extensions

Comments and references added by N. J. A. Sloane, Oct 04 2014