|
%I #22 Dec 13 2019 13:46:18
%S 1,2,6,8,15,4,11,5,13,27,37,45,16,7,18,52,64,46,9,40,91,53,44,88,120,
%T 93,108,26,77,12,101,94,106,155,134,57,31,190,71,14,89,33,54,206,150,
%U 117,244,219,241,276,38,62,17,211,243,74,277,307,325,67,306,176,43
%N a(n) is the smallest positive solutions of the congruence x^2 + (x+1)^2 == 0 (mod prime), where prime = A002144(n) (Pythagorean primes).
%C The companion sequence is A212354.
%C There are at most two incongruent solutions of this congruence due to the degree. The fact that there are precisely two such solutions for each prime of the form 4*k+1 (see A002144) is due to the reduction of this problem to one of quadratic residues, namely to X^2 == -1 (mod 2p), with p a prime (see the Nagell reference, given in A210848, pp. 132-3, especially theorem 77), adapted to the quadratic form f(x) = 2*x^2 + 2*x + 1, with discriminant D=-4. This congruence with composite modulus has exactly two incongruent solutions because X^2 == -1 (mod 2) has only the solution +1 modulo 2 (odd numbers), and X^2 == -1 (mod p) has (at least one) solution if the Legendre symbol (-1/p) = +1 (i.e., if -1 is a quadratic residue modulo p). Now (-1/p) = (-1)^(p-1)/2 (see, e.g., the Niven-Zuckerman-Montgomery reference given in A001844, Theorem 3.2 (1), p. 132). Hence there is a solution modulo p iff p == 1 (mod 4). Call the smallest positive one X0, with 0 < X0 < p-1. Then one also has the incongruent solution X1 := p-X0. This implies that there are precisely two incongruent solution of the original congruence modulo 2*p for each 1 (mod 4) prime (see, e.g., Nagell's book, pp. 83-4, Theorem 46). If u is a solution for p = A002144(n) (the existence of u has just been proved) then also the companion v := p-1-u satisfies this congruence, and v is incongruent to u modulo p.
%C Note that x^2 + (x+1)^2 = 4*T(x) + 1, with the triangular numbers A000217.
%C The primes with x^2 +(x+1)^2 = prime (necessarily from A002144) are found under A027862. The corresponding x values are found under A027861. These x values explain the positions n' where a(n') is smaller than a(n'-1) (for n'>=6): determine k with x=A027861(k), and then n' from A027862(k) = A002144(n'). Note that a(n') = x for such values n'. E.g., n'=6 with a(6)=4: x=4=A027861(3), p=41=A027862(3) = A002144(6). These values n' are n' = 1, 2, 6, 8, 14, 19, 30, ...
%C All positive solutions of this congruence are provided by the two sequences with entries u(n,k) = a(n) + k*A002144(n) and v(n,k) = A212354(n) + k*A002144(n), n >= 1, k >= 0. For the cases p = 5, 13 and 17 see A047219, A212160 and A212161, respectively, where the even-indexed numbers are the u(n,k) and the odd-indexed ones the v(n,k) (bisection).
%C 2*a(n) + 1 = A206549(n), the smallest positive nontrivial solution of X^2 == +1 (Modd A002144(n)). For the next larger solution 2*A212354(n) + 1 >= p, hence it does not belong to the restricted residue system Modd A002144(n).
%F a(n) is the smaller of the two smallest positive incongruent solutions of the congruence x^2 + (x+1)^2 = 2*x^2 + 2*x + 1 == 0 (mod A002144(n)), where A002144 lists the primes
%F 1 modulo 4 (primes of the form 4*k+1). For the proof of the existence of a(n) see a comment above. The next larger incongruent companion solution is A212354(n), n >= 1.
%e n=1: a(1)=1 because 1^2 + 2^2 = 5 == 0 (mod 5). The companion solution is (5-1) - 1 = 3 = A212354(1).
%e n=3: a(3)=6 because 6^2 + 7^2 = 85 = 5*17 == 0 (mod 17). The companion is (17-1) - 6 = 10 = A212354(3).
%e n=14: a(14)=7 because p=A002144(14) = 113 = A027862(5), and 49^2 + 50^2 = 113. The companion is (113-1) - 7 = 105 = A212354(14).
%Y Cf. A047219(1)=a(1), A212160(1)=a(2), A212161(1)=a(3), A212354 (companions), A206549.
%K nonn
%O 1,2
%A _Wolfdieter Lang_, May 10 2012
|
