A320159 Number of positive integers x < prime(n)/2 such that (x^2 mod prime(n)) > (4*x^2 mod prime(n)).

0, 0, 1, 2, 2, 3, 4, 5, 4, 7, 9, 9, 10, 11, 9, 13, 13, 15, 17, 14, 18, 22, 19, 22, 24, 25, 28, 25, 27, 28, 34, 30, 34, 36, 37, 41, 39, 41, 36, 43, 42, 45, 41, 48, 49, 54, 54, 59, 54, 57, 58, 52, 60, 59, 64, 59, 67, 73, 69, 70, 72, 73, 78, 68, 78, 79, 84, 84, 84, 87, 88, 80, 96, 93, 96, 87, 97, 99, 100, 102

Offset: 1

Author

Qing-Hu Hou and Zhi-Wei Sun, Oct 06 2018

Keywords

• nonn

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

Examples

			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).
		

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.

Crossrefs

Cf. A000040, A000290, A319311.

Programs

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}]

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