A334070 Number of even-order elements in the multiplicative group of integers modulo n.

0, 0, 1, 1, 3, 1, 3, 3, 3, 3, 5, 3, 9, 3, 7, 7, 15, 3, 9, 7, 9, 5, 11, 7, 15, 9, 9, 9, 21, 7, 15, 15, 15, 15, 21, 9, 27, 9, 21, 15, 35, 9, 21, 15, 21, 11, 23, 15, 21, 15, 31, 21, 39, 9, 35, 21, 27, 21, 29, 15, 45, 15, 27, 31, 45, 15, 33, 31, 33, 21, 35, 21, 63

Offset: 1

Author

Robert A. Jones, Apr 13 2020

Keywords

• nonn

Comments

The number of even-order elements in a finite abelian group G is |G| - b(|G|), where b is given by A000265. To see this, decompose G as a product of cyclic groups of orders {m_k}. G has [prod_k b(m_k)] elements of odd order, since an element has odd order if and only if all its components have odd order, and each C_m factor has b(m) elements of odd order. Since b can be pulled outside the product, G has b(|G|) elements of odd order. Using that the order of (Z/nZ)^x is phi(n), we obtain a(n) = phi(n) - b(phi(n)).

Since phi(n) is even when n > 2, a(n) is odd when n > 2.

Examples

			For n = 10, the elements of (Z_n)^x with even order are 3 (order 4), 7 (order 4), and 9 (order 2). Thus, a(10) = 3.
		

Crossrefs

Cf. A000010, A053575, A129527, A331739 (number of even-order elements in Z_n).

Programs

Maple

a:= n-> (t-> t-t/2^padic[ordp](t, 2))(numtheory[phi](n)):
seq(a(n), n=1..80);  # Alois P. Heinz, Apr 14 2020

Mathematica

a[n_] := Length@
  Select[Range[n] - 1, EvenQ[MultiplicativeOrder[#, n]] &];
oddPart[n_] := n/2^IntegerExponent[n,2];
a[n_] := EulerPhi[n] - oddPart[EulerPhi[n]];

Formula

a(n) = A000010(n) - A053575(n) = A331739(A000010(n)).