|
%I #21 Jul 23 2021 10:15:58
%S 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,
%T 25,27,28,34,30,34,36,37,41,39,41,36,43,42,45,41,48,49,54,54,59,54,57,
%U 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
%N Number of positive integers x < prime(n)/2 such that (x^2 mod prime(n)) > (4*x^2 mod prime(n)).
%C 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.
%C 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.
%C The conjecture was confirmed by Q.-H. Hou, H. Pan and Z.-W. Sun in 2021. - _Zhi-Wei Sun_, Jul 22 2021
%H Qing-Hu Hou and Zhi-Wei Sun, <a href="/A320159/b320159.txt">Table of n, a(n) for n = 1..10000</a>
%H Qing-Hu Hou, Hao Pan and Zhi-Wei Sun, <a href="http://arxiv.org/abs/2107.08984">A new theorem on quadratic residues modulo primes</a>, arXiv:2107.08984 [math.NT], 2021.
%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1809.07766">Quadratic residues and related permutations</a>, arXiv:1809.7766 [math.NT], 2018.
%e 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).
%e 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).
%t 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}]
%o (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
%Y Cf. A000040, A000290, A319311.
%K nonn
%O 1,4
%A _Qing-Hu Hou_ and _Zhi-Wei Sun_, Oct 06 2018
|
