OFFSET
1,4
COMMENTS
Conjecture: Let p > 3 be a prime and let b be any integer. For a = 2,...,p-1 let I(a,b) denote the number of positive integers x < p/2 with (x^2+b mod p) > (a*x^2+b mod p). Then both S = {I(a,b): 1 < a < p and (a/p) = 1} and T = {I(a,b): 1 < a < p and (a/p) = -1} have cardinality 1 or 2 according as p is congruent to 1 or 3 modulo 4, where (a/p) is the Legendre symbol. Moreover, the set S deos not depend on the value of b.
For any prime p == 1 (mod 4), we have q^2 == -1 (mod p) for some integer q, hence ((q*x)^2 mod p) > (a*(q*x)^2 mod p) if and only if (x^2 mod p) < (a*x^2 mod p). Thus, for each a = 2,...,p-1 there are exactly (p-1)/4 positive integers x < p/2 such that (x^2 mod p) > (a*x^2 mod p). Thus I(a,0) = (p-1)/4 for all a = 2,...,p-1.
The conjecture was confirmed by Q.-H. Hou, H. Pan and Z.-W. Sun in 2021. - Zhi-Wei Sun, Jul 22 2021
LINKS
Qing-Hu Hou and Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Qing-Hu Hou, Hao Pan and Zhi-Wei Sun, A new theorem on quadratic residues modulo primes, arXiv:2107.08984 [math.NT], 2021.
Zhi-Wei Sun, Quadratic residues and related permutations, arXiv:1809.7766 [math.NT], 2018.
EXAMPLE
a(3) = 1 since prime(3) = 5, (1^2 mod 5) < (4*1^2 mod 5) and (2^2 mod 5) > (4*2^2 mod 5).
a(4) = 2 since prime(4) = 7, (1^2 mod 7) < (4*1^2 mod 7), (2^2 mod 7) > (4*2^2 mod 7) and (3^2 mod 7) > (4*3^2 mod 7).
MATHEMATICA
Inv[p_]:=Inv[p]=Sum[Boole[Mod[x^2, p]>Mod[4x^2, p]], {x, 1, (p-1)/2}]; Table[Inv[Prime[n]], {n, 1, 80}]
PROG
(PARI) a(n) = my(p=prime(n), m=p\2); if (n==1, m--); sum(k=1, m, lift(Mod(k, p)^2) > lift(Mod(2*k, p)^2)); \\ Michel Marcus, Oct 07 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Qing-Hu Hou and Zhi-Wei Sun, Oct 06 2018
STATUS
approved