cp's OEIS Frontend

This sequence applies to the odd m >= 3 numbers collected in A327922 with 4 dividing phi(2*m) = phi(m). The analog for even m is: every even numbers m >= 4 has even phi(2*m)/2 = A062570(m/2) = 2*A055034(m/2), This means that phi(2*m)/4 = A055034(m/2), for every even m >= 4.

The old name was A196445(n)/2.

From Wolfdieter Lang, Nov 12 2019: (Start)

These are the odd numbers m for which the degree of the algebraic number sin(Pi/(2*m)) (the degree of its minimal polynomial), given by A055035(2*m), is odd. Because A055035(1) = 1, there is just this other instance with odd A055035.

This sequence {a(n)} consists for n >= 2 of all powers >= 1 of each prime p == 3 (mod 4) from A002145, sorted into increasing order. This follows from the factorization of odd m >= 3, and that phi(m)/2 has to be odd.

For a(n), with n >= 2, there is exactly one pair of solutions x = +1 and -1 (the trivial solution) of the congruence x^2 == +1 (mod a(n)), and there is no solution of the congruence x^2 == -1 (mod a(n)). The proof starts with showing this for p == 3 (mod 4). It can be shown that the square 1 appears only for x = 1 if x runs through 1, ..., (p-1)/2. The other x range (p+1)/2, ..., p-1, which has the same squares (mod p), can, by reading backwards, be interpreted as the -x partners of x from the first range. The Legendre symbol (-1, p) = -1 shows the second claim. Then one applies the lifting theorem for powers of primes (see Apostol, Theorem 5.30, p. 121), where only its part (a) is needed, and the step by step lifting to each prime power is unique.

For a(1) = 1 there is just one solution x = 0 of the congruence x^2 == +1 (mod 1), and also of x^2 == -1 (mod 1).

The complementary sequence with odd m >= 3 and even phi(m)/2 is given in A327922.

(End)

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.

For the modified congruence modulo n of Brändli and Beyne, called mod* n, see the link. See also the comments in A333856 for this reduced residue system mod* n, called RRS*(n), for n >= 1.

The odd members of RRS*(n) are denoted by RRS*odd(n), similarly, RRS*even(n) are the even elements of RRS*(n). E.g., RRS*odd(5) = {1} and RRS*even(5) = {2}. Therefore the odd number 5 can be called balanced in the reduced mod* system, because #RRS*odd(5) = 1 = #RRS*even(5).

All even numbers are unbalanced because RRS*(2*m) has only odd members, for m >= 1.

b = 1, with RRS*(1) = {0} is unbalanced, and for odd numbers b >= 3 to be balanced one needs integer phi(b)/4 because #RRS*(b) = phi(b)/2 (phi = A000010). The odd integers >= 3 with integer phi(b)/4 are given in A327922. The present sequence gives, for n >= 2, a proper subset of A327922 consisting of odd numbers b with an unequal number of odd and even elements (unbalanced odd b). Therefore, the condition phi(b)/4 integer for odd b is necessary but not sufficient for such odd b in the reduced mod* system.