cp's OEIS Frontend

The length of row n is given by A329586.

These two congruences arise as special solutions of the complex congruence z^2 == +1 (mod m), for m >= 1. In the present table all representative solutions are collected for z = a + b*i, with a*b = 0, i.e., real or pure imaginary solutions. One could record the solutions as (a, 0) and (0, b) for the first and second congruence, respectively. Only for m = 1 is a = b, namely 0. The other complex solutions z with nonvanishing a*b are collected in table A329587.

In the example section the nonnegative representative solutions are given. A solution x followed by a bar indicates that it solves the congruence x^2 == -1 (mod m). Pairs of solutions which are symmetric with respect to the middle of a row correspond to +x (first half of the solutions) and -x (second half), modulo m. For m = 2 the two congruences become identical, with one solution x = 1 == -1 (mod 2). They are however recorded as 1 (= (1, 0)) and 1| (= (0, 1)) corresponding to the two solutions z = 1 and z = i. But for counting of solutions for composite moduli the prime 2 is considered as having 1 solution.

E.g., n = 5: 1, 2|, 3|, 4 give the pair 1 and 4 == -1 (mod 5) solving the first congruence (the trivial two solutions), and 2 and 3 == -2 (mod 5) give the pair solving the second congruence.

The number of solutions S(m) given in A329586 is as follows: S(1) = 1, and S(2) = 2 (special), S(m) = 2^{r2(e2) + r1 + r3} + delta_{r2(e2),0} * delta_{r3,0} * 2^r1, for m >= 3, where r1 = r1(m) and r3 = r3(m) are the number of odd primes in the radical of m (the set of distinct odd primes in m) congruent to 1 and 3 modulo 4, respectively, r2(e2) = 0, 1 and 2 if the power e2 of the even prime 2 is 0 (odd m case) or 1, 2 and >= 3, respectively, and delta is the Kronecker symbol. The two terms refer to the first and second congruence. S(m) is always a nonnegative power of 2. This formula can be proved by starting with the standard theorem on congruences with composite moduli (e.g., Apostol, Theorem 5.28, pp, 118-119) and employing the lifting theorem for powers of primes given there as Theorem 5.30, p. 121. For the odd primes (A002144 and A002145) only part (a) of the theorem is needed, leading to a unique lifting of each solution with prime modulus from one power to the next higher one. For the even prime 2 one needs both alternatives of part (b). This leads from the two p = 2 solution +1 (== -1 (mod 2)) to be considered as (1, 0) and (0, 1) to the result: 2 solution for m = 2 (special case), 2 solutions for m = 2^2 (a twofold lifting for (1, 0), and (0,1) cannot be lifted to m = 4, due to case (b_2) of the theorem) and 4 solutions for 2^e2, with e2 >= 3.

This sequence is a proper subsequence of A257591 where also odd numbers, not a prime power, and 1 (mod 4) divisors involving only primes congruent to 3 modulo 4 are included, like 63, 99, 147, 171, 189, ... .

This sequence gives all odd moduli m that have solutions of the complex congruence z^2 = +1 (mod m), with z = a + b*i, where a, b are positive integers (nonvanishing a*b case). For a proof one can use the formula for the number of solutions of this congruence for a*b vanishing, given in A329586 without powers of 2 (e2 = 0) and subtract it from the formula for the number of all representative solutions with modulus m >= 1 which is S(m) = 1 if m = 1, and S(m) = 2^(2*r1(m) + r3(m)), with r1(m) and r3(m) the number of distinct primes 1 (mod 4) (A002144) and 3 (mod 4) (A002145), respectively. This becomes the number of representative solutions 2^(r1(m) + r3(m))*(2^(r1(m)) - 1) - delta(r3(m), 0)*2^(r1(m))), with the Kronecker symbol. This shows that for odd modulus m >= 3 and nonvanishing a*b there is no solution if r1(m) = 0 and r3 >= 1. Moduli which are powers of a single prime have only solutions with a or b vanishing.

See A329587 for all moduli m with solutions of z^2 = +1 (mod m), with z = a + b*i and nonvanishing a*b, where all even numbers >= 4 appear.

For the representative solutions of this congruence with a*b = 0 see A329585 for all positive moduli m.

For the representative solutions of this congruence for all m >= 1 see A227091.

This sequence gives one half of the row lengths of the irregular triangle A329587.

For the number of representative solutions of this congruence for all positive moduli m and vanishing a*b see A329586.

The formula for the number of representative solutions a(n), with modulus m = m(n), given in A329587, can be found from the number of all such solutions for m = m(n) given in A227091 after subtracting the number of solutions with a*b = 0 given in A329586. For odd m = m(n) this is S(m) = 2^(r1(m) +r3(m))*(2^r1(m) - 1) - delta(r3(m), 0)*2^(r1(m)), with r1(m) and r3(m) the number of distinct primes 1 (mod 4) and 3 (mod 4) in the prime number factorization of m respectively, and delta is the Kronecker symbol. For even m this is S(m) = 2^(r1(m) + r3(m))*(2^(1+r1(m)) - 1) - delta(r3(m), 0)*2^(r1(m)) if m/2 is odd (e2 = 1), and otherwise S(m) = 2^(r2(e2(m)) + r1(m) + r3(m))*(2^(1 + r1(m) + r3(m)) - 1), with r2(e2(m)) = 1 or 2 if e2(m) = 2 or >= 3, if m/2^(e2(m)) is odd.