login
A334070
Number of even-order elements in the multiplicative group of integers modulo n.
0
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.
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
KEYWORD
nonn
AUTHOR
Robert A. Jones, Apr 13 2020
STATUS
approved