# Seq. of largest QR mod the primes

Don Reble djr at nk.ca
Sat Nov 27 15:10:15 CET 2004

```> 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
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

```