login
All positive integer moduli a(n) for which the congruence x^2 == -5 (mod a(n)) is solvable for integer x (representatives from {0, 1, ..., a(n)-1}); ordered increasingly.
6

%I #13 Sep 17 2023 06:11:07

%S 1,2,3,5,6,7,9,10,14,15,18,21,23,27,29,30,35,41,42,43,45,46,47,49,54,

%T 58,61,63,67,69,70,81,82,83,86,87,89,90,94,98,101,103,105,107,109,115,

%U 122,123,126,127,129,134,135,138,141,145,147,149,161,162,163,166,167,174,178,181,183,189,201,202

%N All positive integer moduli a(n) for which the congruence x^2 == -5 (mod a(n)) is solvable for integer x (representatives from {0, 1, ..., a(n)-1}); ordered increasingly.

%C This sequence includes A139513, that is, Legendre(-5, p) = +1 for odd primes not 5, that is, primes congruent to {1, 3, 7, 9} mod 20. Here 5 is a member of the sequence with solution x = 0.

%C The primes of this sequence are given in A240920.

%C The present sequence gives the numbers of the form 2^a*5^b*Product_{j=1..m} (p_j)^e(j), with a and b from {0, 1}, p_j a prime from {1, 3, 7, 9} (mod 20), i.e., from A139513, m >= 0 and e(j) >= 0 (this includes the number 1). These numbers are ordered increasingly.

%C This follows from the Legendre-symbol(-5, p)= +1 and the lifting theorem (see, e.g., Apostol, Theorem 5.30, p. 121-2) for p = 2 and 5 (no lifting for the solutions for p = 2 and p = 5), and the unique lifting for the primes satisfying Legendre-symbol(-5, p) = +1.

%C Therefore the number of representative solutions x from {0, 1, ..., a(n)-1}, denoted by M(a(n)), is 1 for precisely four cases: a(1) = 1 (x = 0), a(2) = 2 (x = 1), a(4) = 5 (x = 0) and a(8) = 10 = 2*5 (x = 5). For each of the mentioned prime powers there are just 2 solutions. This implies that for the number of solutions in the general a(n) case, n not 1, 2, 4, 8, only the primes p_j are of interest: M(a(n)) = 2^m(n).

%C For these solutions x see A343239, and for the multiplicity M(a(n)) see A343240.

%C This congruence is needed to find all proper solutions of the positive definite binary quadratic form of discriminant Disc = -20 = -4*5 representing k = a(n). The solutions x lead to the so-called representative parallel primitive forms (rpapfs). See A344231 for more details.

%C For a bisection see A344231 and A344232, related to integer solutions of X^2 + 5*Y^2 = A344231(k) and 2*X^2 + 2*X*Y + 3*Y^2 = A344232(k).

%D Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, pp 121, 122.

%F There exists at least one x from {0, 1, ..., m-1} satisfying x^2 + 5 == 0 (mod m), for positive integer m. These m values are then ordered increasingly as (a(n))_{n>=1}.

%e a(3) = 3: two solutions 1 and 2.

%e a(7) = 3^2 = 9: two solutions 2 and 7.

%e a(8) = 10 = 2*5 only one solution 5.

%e a(53) = 135 = 5*3^3: two solutions 20 and 115.

%o (PARI) isok(k) = issquare(Mod(-5, k)); \\ _Michel Marcus_, Sep 17 2023

%Y Cf. A139513, A240920, A343239, A343240, A344231, A344232.

%K nonn,easy

%O 1,2

%A _Wolfdieter Lang_, May 16 2021