[seqfan] Re: Sequence Idea

[David Wilson]

Thank you, Neil, for supporting your position. I stand corrected.

The two definitions of "n is a quadratic residue mod m" under discussion are as follows:
Unrestricted: n = k^2 (mod m)
Restricted: n = k^2 (mod m) and gcd(n, m) = 1.

I assume there are no other common definitions in the literature (i.e. n = k^2 (mod m), n != 0 (mod m) is not common enough to consider).

Both Wikipedia and MathWorld* "Quadratic Residue" articles give the unrestricted definition above as the main definition, but include citations for the restricted definition. I therefore concede that the restricted definition is a common enough, if not the most common, definition. Live and learn.

Given this, I agree with Neil that we should include a variant of the gap sequence (A248222) using the restricted definition.  I also agree with Neil that the two common definitions make the name "Maximal gap between quadratic residues mod n" ambiguous. I agree with Neil's proposal for "Maximal gap between squares mod n" for A248222, and propose "Maximal gap between quadratic residues mod n" for the variant sequence, with a comment defining quadratic residue as coprime to n, to allay any confusion.

To clear up a previous misstatement of mine: Under the restricted definition, 0 is still a quadratic residue mod 1 (but no modulus > 1), since gcd(0, 1) = 1. This means that a(1) is in fact defined in the variant gap sequence (a(1) = 1).

Note: I use Wikipedia and MathWorld as handy data points, not final authorities.

Wikipedia "Quadratic residue":
For this reason some authors add to the definition that a quadratic residue q must not only be a square but must also be relatively prime to the modulus n.

MathWorld "Quadratic residue":
Care must be taken when dealing with quadratic residues, as slightly different definitions are also apparently sometimes used. For example, Stangl (1996) adopts the apparently nonstandard definition of quadratic residue as an integer x satisfying 0<x<p such that x^2=q (mod p) and x is relatively prime to p.


> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil
> Sloane
> Sent: Saturday, October 04, 2014 3:09 PM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: Sequence Idea
> 
> David said:
> > The quadratic residues always include 0 and need not be coprime to the
> modulus.
> This is not the usual definition, which is the following:
> 
> Ireland and Rosen, page 50: "If (a,m)=1, a is called a quad res mod m if
> the congruence x^2 == a (mod m) has a solution. Otherwise a is called a
> quad nonresidue mod m."
> 
> This excludes 0 and does require relatively prime.
> 
> It is pointless to argue about definitions.  The OEIS should contain all
> possible interpretations of this notion.