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 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.