A097160

[Max]

On 4/18/06, Don Reble <djr at nk.ca> wrote:
> Seqfans:
>
> > %S A097160 5,17,53,193,457,2153,4481,9857,17041,23473
> > %N A097160 Greatest prime p such that there are n consecutive
> >       quadratic residues mod p.
> > %e A097160 Only the first three primes have no consecutive quadratic
> >       residues, etc.
>
>     I think this means that 53 has three consecutive quadratic resides,
>     but not four; and that each larger prime has four consecutives.
>
>     How might one prove that each larger prime has four consecutives?

Suppose we are looking for k consecutive quadratic residues.
Let us consider consecutive k-tuples:
t_1 = { 1,2,...,k }
t_2 = { 2,3,...,k+1 }
...
t_x = { x,x+1,...,x+k-1 }
...

Due to the quadratic reciprocity law, every tuple t_x defines a set
S_x of residues modulo M_x = lcm(x,x+1,...,x+k-1) such that
if a prime p belongs to S_x then the tuple t_x represents k
consecutive residues modulo p.
Rough probabilistic arguments suggest that the size of S_x is about M_x / 2^k.

Now if the sets S_1,S_2,...,S_m form a complete set of residues then
any prime greater than m+k will fall into one of these sets meaning
that p has k consecutive residues.

So for a fixed k to prove that all large primes possess k consecutive
quadratic residues, it is enough to show that there exists m such that
S_1,S_2,...,S_m form a complete set of residues.

Max