cp's OEIS Frontend

See A329585 for details and examples (there n is called m).

For the number of all representative solutions z^2 = +1 (mod n), for n >= 1, with z = a + b*i, where a and b are nonnegative integers, see A227091.

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.

The length of row n is given in 2*A329588(n).

This table should be considered together with A329585 which gives the solutions of this congruence with a*b = 0 (real or pure imaginary solutions) for each m >= 2. Only for m = 1 is a = b, namely (a, b) = (0, 0).

Because z^2 = (a^2 - b^2) + 2*a*b*i, this is equivalent to the two congruences (i) a^2 - b^2 == 1 (mod m) and (ii) 2*a*b == 0 (mod m). Here with nonvanishing a*b.

Because with each solution z = a + b*i, with representative a and b from {1, 2, ..., m-1}, also -z = -(a + b*i), zbar:= a - b*i and -zbar = -a + b*i are solutions modulo m.

This table T(n, k) lists all pairs (a,b) for those even m = m(n) which have solutions with nonvanishing a*b.

The solutions for odd numbers start with m = 15, 35, 39, 45, 51, 55, ... . See A329589 which is a proper subsequence of A257591. For example, m = 63 is not present in A329589.

There is a symmetry (a, b) <-> (m-a, m-b) == (-a, -b) (mod m) around the middle of the pairs in each row. Such pairs correspond to z and -z (mod m). Because of this symmetry one considers first a > b (a = b cannot occur for m >= 2, see above), and later adds the a < b solutions.

Obvious solutions for each solvable even m are for m/2 odd (m/2+1, m/2) with companion (m/2-1, m/2), and in addition, if m/(2^e2) is odd, for e2 >= 2, (m-1, m/2) with companion (1, m/2) (for m = 4 this coincides with the first case).

For (positive) even m, m = 2*M, there is the following connection to Pythagorean triples (X, Y, Z). We say triples, not triangles, because X may also become negative. Eq.(i) from above becomes (i') a^2 - (b^2 + 1) = qhat*2*M, with integer qhat. This implies that a and b have opposite parity, i.e., (-1)^(a+b) = -1. The other eq. (ii) is now (ii') a*b = q*M, with integer q. Thus (q, qhat) = (Y/m, (X-1)/m).

Case A) Primitive Pythagorean triples (pPT). If a > b and gcd(a, b) = 1 then the conditions for primitive Pythagorean triples are satisfied. Set 0 < X = a^2 - b^2 = 1 + 2*qhat*M, 0 < Y = 2*a*b = 2*q*M, 0 < Z = a^2 + b^2 = r^2 (Y is even, X is odd, and Z is odd). One could interchange the role of X and Y (for triangles a catheti exchange). Note that the radius r is in general not an integer. E.g., for m=4 (a, b) = (3, 2) has r = sqrt(13), (q, qhat) = (3, 1), pPT = (5, 12, 13).

Note that the companion triple for a < b (z -> -z) has negative X. In this example the companion of (a, b) = (3, 2) is (-a, -b) (mod 4) == (4-3, 4-2) = (1, 2), and the companion pPT = (-3, 4, 5).

Case B) m even, a > b, (-1)^(a+b) = -1, gcd(a, b) = g >= 2, leads to imprimitive Pythagorean triples (ipPT) for solutions of (i') and (ii'). The first example appears for m = 20, M = 10, (a, b) = (15, 12), g = 3, (q, qhat) = (18, 4), r = 3*sqrt(41), ipPT = (81, 360, 369) = (3^2)*(9, 40, 41). The companion has (a, b) = (5, 8), which is primitive, (q, qhat) = (4, -2), with pPT = (-39, 80, 89).

In A226746 the m values with more than two representative solutions of z^2 == +1 (mod m) are given. For the corresponding solutions one has also to consider the irregular triangle A329588(n).

The number of all representative solutions z^2 == +1 (mod m), for m >= 1, is found by combining A329586 and A329588, and is given in A227091.

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.