OFFSET
1,1
COMMENTS
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).
FORMULA
Row n, with m = m(n), of this irregular triangle T(n, k), with row length A329588(n), lists all pairs (a, b) which solve z^2 == +1 (mod m), with z = a + b*i, and nonvanishing a*b, sorted with a > b pairs in both halves in the example separated by a | symbol) first with increasing a, then increasing b.
EXAMPLE
The irregular triangle T(n, k) begins: (A | symbol separates a > b and a < b pairs, a star indicates that a pair is not relatively prime. For n = 10, 12 and 15 two rows are given with corresponding q >= 7.)
n, m \ q 1 2 3 4 5 6 ...
-----------------------------------------------------------------------
1, 4: (3,2) | (1,2)
2, 6: (4,3) | (2,3)
3, 8: (5,4) (7,4) | (1,4) (3,4)
4, 10: (5,2) (6,5) | (4,5) (5,8)
5, 12: (7,6) (11,6) | (1,6) (5,6)
6, 14: (8,7) | (6,7)
7, 15: (5,3) (10,3) | (5,12) (10,12)*
8, 16: (9,8) (15,8) | (1,8) (7,8)
9, 18: (10,9) | (8,9)
10, 20: (5,2) (11,10) (15,2) (15,8) (15,12)* (19,10) |
(1,10) (5,8) (5,12) (5,18) (9,10) (15,18)*
11, 22: (12,11) | (10,11)
12, 24: (13,12) (17,12) (19,12) (23,12) |
(1,12) (5,12) (7,12) (11,12)
13, 26: (13,18) (14,13) | (12,13) (13,8)
14, 28: (15,14) (27,14) | (1,14) (13,14)
15, 30: (10,3) (16,15) (20,3) (25,12) (25,18) (26,15)
(4,15) (5,12) (5,18) (10,27) (14,15) (20,27)
16, 32: (17,16) (31,16) | (1,16) (15,16)
17, 34: (17,4) (18,17) | (16,17) (17,30)
18, 35: (15,7) (20,7) | (15,28) (20,28)
...
----------------------------------------------------------------------------
n=1, m=4: (1 + 2*i)^2 = (1 - 4) + 2*2*i == -3 (mod 4) == 1 (mod 4).
(3 + 2*i)^2 = (9 - 4) + 12*i == 1 (mod 4).
----------------------------------------------------------------------------
For even m the Pythagorean triples (X,Y,Z) are:
m\ pPT and ipPT*, also with companions with negative X, separated by a |
---------------------------------------------------------------------------
4: (5,12,13) | (-3, 4, 5)
6: (7,24,25) | (-5,12,13)
8: (9,40,41) (33,56,65) | (-15,8,17) (-7,24,25)
10: (21,20,29) (11,60,61) | (-9,40,41) (-39,80,89)
12: (13,84,85) (85,132,157) | (-35,12,37) (-11,60,61)
14: (15,112,113) | (-13,84,85)
16: (17,144,145) (161,240,289) | (-63,16,65) (-15,112,113)
18: (19,180,181) | (-17,144,145)
20: (21, 20, 29) (21,220,221) (221,60,229)
(161,240,289) (81, 360,369)* (261,380,461) |
(-99,20,101) (-39,80,89) (-119,120,169)
(-299,180,349) (-19,180,181) (-99,540,549)*
22: (23,264,265) | (-21,220,221)
24: (25,312,313) (145,408,433) (217,456,505) (385,552,673)
(-143,24,145) (-119,120,169) (-95,168,193) (-23,264,265)
26: (105,208,233) (27,364,365) | (-25,312,313) (-155,468,493)
28: (29,420,421) (533,756,925) | (-195,28,197) (-27,364,365)
30: (91,60,109) (31,480,481) (391,120,409)
(481,600,769) (301,900,949) (451,780,901) |
(-209,120,241) (-119,120,169) (-299,180,349)
(-629,540,829) (-29,420,421) (-329,1080,1129)
32: (33,544,545) (705,992,1217) | (-255,32,257) (-31,480,481)
34: (273,136,305) (35,612,613) | (-33,544,545) (-611,1020,1189)
...
----------------------------------------------------------------------------
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Wolfdieter Lang, Dec 14 2019
STATUS
approved