Seq. of largest QR mod the primes

[Don Reble]

> http://web.axelero.hu/fadorjan/qrp.pdf


> Observation 2. ... whenever a[i]<=a[i-1] then p=7 mod 8 [and] if i>4
> then p[i] /= 2 mod 5.

Those are easy to prove. We already know that p=3 mod 4. If p=3 mod 8,
then p-2 is a QR. If also p>3:
    p-1 is even and composite.
    p-2 and smaller are too small for p-2.
So sequence A has to be increasing when p=3 mod 8 and p>3.

Again, p=3 mod 4. If p=2 mod 5 also then p=7 mod 20 and so p-5 is a
quadratic residue. If also p>7:
    p-2 is divisible by 5 and composite.
    p-4 might be prime, but it's 3 mod 4 and so -1 (=p-5) isn't a QR.
    p-6 and smaller are too small for p-5.
So sequence A has to be increasing when p=2 mod 5 and p>7.



> ... every prime number p<=43 turns up in B...

One can prove that each prime is there. Use the fact that for odd primes
p and q: -p is a QR modulo q if q=1 mod 4p, and -p is not a QR if
q=-1 mod 4p. By the C.R.T., there is a residue class
r modulo (2*primorial p), such that r=1 modulo p and r=-1 modulo smaller
primes. R is coprime to (2*primorial p), so by Dirichlet's theorem,
there are primes in r's class, and each time, sequence B has p.



> middle column of Table 3 ... the first three ... primes in each of
> the 7 groups are ... modulo 120 ... { 101, 103, 119 }

One can prove that the third prime is 71 or 119 modulo 120. With that
hint, I refute the conjecture:

         p        a     p mod 120
     11935829  11935828    29
     11935831  11935828    31
     11935871  11935828    71

    108448997 108448996    77
    108448999 108448996    79
    108449039 108448992   119

But those two patterns are rare, especially the latter. Are there any
others? Can we prove anything?


--
Don Reble  djr at nk.ca