cp's OEIS Frontend

A248222 Maximal gap between quadratic residues mod n.

%I A248222 #46 Feb 16 2025 08:33:23
%S A248222 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,
%T A248222 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,
%U A248222 13,7,5,7,12,5,5,7,8,11,6,7,15,3,6,8,12,13,6,11,16,7,6
%N A248222 Maximal gap between quadratic residues mod n.
%C A248222 "Maximal gap between squares mod n" would be a less ambiguous definition.
%C A248222 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.
%C A248222 See A248376 for the variant with the additional restriction that the residue be coprime to the modulus. - _M. F. Hasler_, Oct 08 2014
%D A248222 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.]
%D A248222 F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 45.
%D A248222 G. B. Mathews, Theory of Numbers, 2nd edition. Chelsea, NY, p. 32. [Does not require gcd(q,n)=1.]
%D A248222 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.]
%D A248222 J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 270. [Does not require gcd(q,n)=1.]
%H A248222 Alois P. Heinz, <a href="/A248222/b248222.txt">Table of n, a(n) for n = 1..10000</a>
%H A248222 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>
%H A248222 Wikipedia, <a href="http://en.wikipedia.org/wiki/Quadratic_residue">Quadratic residue</a>
%e A248222 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).
%e A248222 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).
%o A248222 (PARI) (DD(v)=vecextract(v,"^1")-vecextract(v,"^-1")); a(n)=vecmax(DD(select(f->issquare(Mod(f,n)),vector(n*2,i,i))))
%Y A248222 Cf. A063987, A130290, A088190, A088191, A088192.
%K A248222 nonn
%O A248222 1,3
%A A248222 _David W. Wilson_ and _M. F. Hasler_, Oct 04 2014
%E A248222 Comments and references added by _N. J. A. Sloane_, Oct 04 2014