OFFSET
1,3
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
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
EXAMPLE
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).
PROG
(PARI) (DD(v)=vecextract(v, "^1")-vecextract(v, "^-1")); a(n)=vecmax(DD(select(f->issquare(Mod(f, n)), vector(n*2, i, i))))
CROSSREFS
KEYWORD
nonn
AUTHOR
David W. Wilson and M. F. Hasler, Oct 04 2014
EXTENSIONS
Comments and references added by N. J. A. Sloane, Oct 04 2014
STATUS
approved