cp's OEIS Frontend

A241472 a(n) = |{0 < k < sqrt(prime(n)): k^2 + 1 is a quadratic residue modulo prime(n)}|.

%I A241472 #12 Apr 24 2014 09:00:07
%S A241472 0,0,0,1,1,1,1,2,1,1,3,2,4,2,3,3,3,1,5,5,4,6,5,5,3,5,5,3,3,4,7,3,7,4,
%T A241472 6,7,7,4,4,3,6,8,8,6,5,8,7,8,6,6,8,11,8,6,7,7,5,9,2,8,3,11,10,8,6,8,7,
%U A241472 10,5,8,8,9,13,10,10,6,6,10,11,10
%N A241472 a(n) = |{0 < k < sqrt(prime(n)): k^2 + 1 is a quadratic residue modulo prime(n)}|.
%C A241472 a(n) > 0 for all n > 3. In fact, for any prime p > 5 one of 1^2 + 1 = 2, 2^2 + 1 = 5 and 3^2 + 1 = 10 is a quadratic residue modulo p. Similarly, if p > 7 is a prime not equal to 19, then k^2 - 1 is a quadratic residue modulo p for some positive integer k < sqrt(p). In fact, for any prime p > 7, one of 2^2 - 1 = 3, 3^2 - 1 = 8 and 5^2 - 1 = 24 is a quadratic residue modulo p.
%C A241472 See also A239957 for a similar conjecture involving primitive roots modulo primes. Note that a primitive root modulo an odd prime p must be a quadratic nonresidue modulo p.
%H A241472 Zhi-Wei Sun, <a href="/A241472/b241472.txt">Table of n, a(n) for n = 1..10000</a>
%e A241472 a(6) = 1 since 3^2 + 1 = 10 is a quadratic residue modulo prime(6) = 13.
%e A241472 a(7) = 1 since 1^2 + 1 = 2 is a quadratic residue modulo prime(7) = 17.
%e A241472 a(9) = 1 since 1^2 + 1 = 2 is a quadratic residue modulo prime(9) = 23.
%e A241472 a(10) = 1 since 2^2 + 1 = 5 is a quadratic residue modulo prime(10) = 29.
%e A241472 a(18) = 1 since 2^2 + 1 = 5 is a quadratic residue modulo prime(18) = 61.
%t A241472 a[n_]:=Sum[If[JacobiSymbol[k^2+1,Prime[n]]==1,1,0],{k,1,Sqrt[Prime[n]-1]}]
%t A241472 Table[a[n],{n,1,80}]
%Y A241472 Cf. A000040, A002522, A239957, A241492.
%K A241472 nonn
%O A241472 1,8
%A A241472 _Zhi-Wei Sun_, Apr 23 2014