login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A248222 Maximal gap between quadratic residues mod n. 2
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 (list; graph; refs; listen; history; text; internal format)
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

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

Sequence in context: A286104 A137779 A191246 * A107918 A242392 A002963

Adjacent sequences:  A248219 A248220 A248221 * A248223 A248224 A248225

KEYWORD

nonn,changed

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 06:39 EDT 2019. Contains 328292 sequences. (Running on oeis4.)