A329585 Irregular triangle read by rows: representative solutions of the congruences x^2 - 1 == 0 (mod m) or (inclusive) x^2 + 1 == 0 (mod m), for m >= 1.

0, 1, 1, 2, 1, 3, 1, 2, 3, 4, 1, 5, 1, 6, 1, 3, 5, 7, 1, 8, 1, 3, 7, 9, 1, 10, 1, 5, 7, 11, 1, 5, 8, 12, 1, 13, 1, 4, 11, 14, 1, 7, 9, 15, 1, 4, 13, 16, 1, 17, 1, 18, 1, 9, 11, 19

Offset: 1

Author

Wolfdieter Lang, Dec 14 2019

Keywords

• nonn
• easy
• tabf

Comments

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.

Examples

			The irregular triangle T(m, k) begins: (a bar after a number indicates a solution of x^2 == -1 (mod m))
m/k  1   2   3  4 ...          A329586(m)
-----------------------------------------
1:   0                             1
2:   1   1|                        2
3:   1   2                         2
4:   1   3                         2
5:   1   2|  3|  4              2 + 2 = 4
6:   1   5                         2
7:   1   6                         2
8:   1   3   5   7                 4
9:   1   8                         2
10:  1   3|  7|  9              2 + 2 = 4
11:  1  10                         2
12:  1   5   7  11                 4
13:  1   5|  8| 12              2 + 2 = 4
14:  1  13                         2
15:  1   4  11  14                 4
16:  1   7   9  15                 4
17:  1   4| 13| 16              2 + 2 = 4
18:  1  17                         2
19:  1  18                         2
20:  1   9  11  19                 4
...
-----------------------------------------
Number of solutions:
m = 2, 2 solutions (z = 1, z = i) (special case).
m = 6 = 2*3: r1 = 0, e2 = 1, r2(e2) = 0, r3 = 1, hence 2^1 + 0 = 2 solutions.
m = 13 == 1 (mod 4): r1 = 1, e2 = 0 = r2(e2), r3 = 0, hence 2^{0+1+0} + 1*1*2^1 = 2 + 2 = 4 solutions.
m = 20 = 2^2*5: e2 = 2, r2(e2) = 1, r1 = 1, r3 = 0, hence 2^{1+1+0} + 0*1*2^1 = 2^2 = 4 solutions of  x^2 == +1 (mod 20) only.
m = 120 = 2^3*3*5: e2 =3, r2(e2) = 2, r3 = 1, r1 = 1, hence 2^{2+1+1} + 0*0*2^1 = 2^4 = 16 solutions of x^2 == +1 (mod 120) only.
-----------------------------------------------------------------------------
The first instance with 8 solutions is
m = 24: 1  5  7  11  13  17  19  23.
The first instance with 8 solutions involving both congruences is
m = 65: 1  8| 14 18| 47|  51  57| 64.
The first instance with 16 solutions is
m = 120: 1, 11, 19, 29, 31, 41, 49, 59, 61, 71, 79, 89, 91, 101, 109, 119.
The first instance for even m with 16 solutions involving both congruences is
m = 2*5*13*17 = 2210: 1 47| 339 441 463| 781 837| 863| 1347| 1373| 1429 1747| 1769 1871 2163| 2209.
------------------------------------------------------------------------------
		

References

• T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1986

Crossrefs

Cf. A002144, A002145, A327922, A329586, A329587, A227091.

Formula

Row m of length A329586(m): Combined representative solutions of x^2 == +1 (mod m) or x^2 == -1 (mod m), sorted increasingly. The smallest nonnegative residue system modulo m is used: [0, 1, ..., m-1]. For the special m = 1 and m = 2 cases see the comment section.