| Displaying 1-5 of 5 results found.
page
1
Row lengths of A329585: number of solutions of the congruences x^2 == +1 (mod n) or (inclusive) x^2 == -1 (mod n), for n >= 1.
+10
5
1, 2, 2, 2, 4, 2, 2, 4, 2, 4, 2, 4, 4, 2, 4, 4, 4, 2, 2, 4, 4, 2, 2, 8, 4, 4, 2, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 2, 4, 8, 4, 4, 2, 4, 4, 2, 2, 8, 2, 4, 4, 4, 4, 2, 4, 8, 4, 4, 2, 8, 4, 2, 4, 4, 8, 4, 2, 4, 4, 4
COMMENTS
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.
FORMULA
a(1) = 1, a(2) = 2 (special case), and for n >= 3: a(n) = 2^{r2(e2) + r1 + r3} + delta_{r2(e2),0} * delta_{r3,0}*2^r1, where r1 = r1(n) and r3 = r3(n) are the number of the distinct odd primes congruent to 1 and 3 modulo 4, respectively, in the prime number factorization of n, and r2(e2) = 0, 1 and 2 if the power e2 of the even prime 2 is 0 (odd n case) or 1, 2 and >= 3, respectively, and delta is the Kronecker symbol. a(n) is always a nonnegative power of 2. (See A329585 for a sketch of the proof.)
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.
+10
4
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
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.
REFERENCES
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1986
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.
EXAMPLE
The irregular triangle T(m, k) begins: (a bar after a number indicates a solution of x^2 == -1 (mod 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.
------------------------------------------------------------------------------
Irregular triangle read by rows: representative solutions (a, b) of the complex congruence z^2 == +1 (mod m), where z = a + b*i = r*exp(i*phi), with nonvanishing a*b, for all positive integers m which have solutions.
+10
3
3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 7, 4, 1, 4, 3, 4, 5, 2, 6, 5, 4, 5, 5, 8, 7, 6, 11, 6, 1, 6, 5, 6, 8, 7, 6, 7, 5, 3, 10, 3, 5, 12, 10, 12, 9, 8, 15, 8, 1, 8, 7, 8, 10, 9, 8, 9, 5, 2, 11, 10, 15, 2, 15, 8, 15, 12, 19, 10, 1, 10, 5, 8, 5, 12, 5, 18, 9, 10, 15, 18, 12, 11, 10, 11, 13, 12, 17, 12, 19, 12, 23, 12, 1, 12, 5, 12, 7, 12, 11, 12
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).
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.
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)
...
----------------------------------------------------------------------------
Odd integers which are not a positive power of a single prime and have at least one prime divisor 1 (mod 4).
+10
3
15, 35, 39, 45, 51, 55, 65, 75, 85, 87, 91, 95, 105, 111, 115, 117, 119, 123, 135, 143, 145, 153, 155, 159, 165, 175, 183, 185, 187, 195, 203, 205, 215, 219, 221, 225, 235, 245, 247, 255, 259, 261, 265, 267, 273, 275, 285, 287, 291, 295, 299, 303, 305, 315, 319, 323, 325, 327, 333, 335, 339, 345
COMMENTS
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.
MATHEMATICA
Select[Range[3, 235, 2], And[! PrimePowerQ@ #, AnyTrue[FactorInteger[#][[All, 1]], Mod[#, 4] == 1 &]] &] (* Michael De Vlieger, Dec 14 2019 *)
PROG
(PARI) isok(k) = if ((k%2) && !isprimepower(k), my(f=factor(k)); sum(i=1, #f~, (f[i, 1] % 4) == 1) >= 1); \\ Michel Marcus, Sep 18 2023
Number of representative solutions (a, b) of the complex congruence z^2 == +1 (mod m) with z = a + b*i and nonvanishing a*b.
+10
2
2, 2, 4, 4, 4, 2, 4, 4, 2, 12, 2, 8, 4, 4, 12, 4, 4, 4, 4, 2, 4, 24, 4, 4, 4, 2, 8, 4, 4, 12, 2, 4, 8, 4, 24, 2, 4, 8, 4, 12, 12, 8, 4, 4, 4, 12, 24, 4, 8, 8, 2, 4, 8, 12, 4, 4, 2, 4, 8, 2, 12, 12, 24, 8, 4, 4, 12, 4, 8, 4, 4, 12, 4, 2, 4, 48
COMMENTS
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.
FORMULA
a(n) is the number of solutions (a, b) of the congruence z^2 == +1 (mod m(n)), with z = a + b*i and a*b not equal to 0, for n >= 1. For m = m(n) see A329587: it is the sequence of even numbers >= 4 combined with the odd numbers from A329589, sorted increasingly.
EXAMPLE
n = 1, m = 4: a(1) = S(4) = 2^1 *(2^1 - 1) = 2.
n = 2, m = 6 = 2*3: a(2) = S(6) = 2^(0+1)*(2^1 - 1) - 0 = 2.
n = 3, m = 8 = 2^3: a(3) = S(8) = 2^2*(2^1 - 1) = 4.
n = 4, m = 10 = 2*5: a(4) = S(10) = 2^(1+0)*(2^(1+1) -1) - 2^1 = 2*3 - 2 = 4.
n = 10, m = 20 = 2^2*5: a(10) = S(20) = 2^(1+1+0)*(2^(1+1+0) - 1) = 4*3 = 12.
n = 15, m = 30 = 2*3*5: a(15) = S(30) = 2^(1+1)*(2^(1+1) - 1) - 0 = 4*3 = 12.
Search completed in 0.009 seconds
| 