login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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