cp's OEIS Frontend

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

%I A334070 #18 Apr 14 2020 20:48:41
%S A334070 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,
%T A334070 15,15,15,21,9,27,9,21,15,35,9,21,15,21,11,23,15,21,15,31,21,39,9,35,
%U A334070 21,27,21,29,15,45,15,27,31,45,15,33,31,33,21,35,21,63
%N A334070 Number of even-order elements in the multiplicative group of integers modulo n.
%C A334070 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)).
%C A334070 Since phi(n) is even when n > 2, a(n) is odd when n > 2.
%F A334070 a(n) = A000010(n) - A053575(n) = A331739(A000010(n)).
%e A334070 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.
%p A334070 a:= n-> (t-> t-t/2^padic[ordp](t, 2))(numtheory[phi](n)):
%p A334070 seq(a(n), n=1..80);  # _Alois P. Heinz_, Apr 14 2020
%t A334070 a[n_] := Length@
%t A334070   Select[Range[n] - 1, EvenQ[MultiplicativeOrder[#, n]] &];
%t A334070 oddPart[n_] := n/2^IntegerExponent[n,2];
%t A334070 a[n_] := EulerPhi[n] - oddPart[EulerPhi[n]];
%Y A334070 Cf. A000010, A053575, A129527, A331739 (number of even-order elements in Z_n).
%K A334070 nonn
%O A334070 1,5
%A A334070 _Robert A. Jones_, Apr 13 2020