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,5

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.

Links

Table of n, a(n) for n=1..73.

Formula

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

Example

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.

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]];

Crossrefs

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

Sequence in context: A233654 A068074 A063195 * A025796 A024163 A029155

Adjacent sequences: A334067 A334068 A334069 * A334071 A334072 A334073

Keyword

nonn

Author

Robert A. Jones, Apr 13 2020

Status

approved