A395683 - OEIS

%I #17 Jun 03 2026 20:36:50

%S 1,1,2,2,2,2,4,4,4,2,8,4,4,4,4,4,8,4,12,4,8,8,20,8,8,4,12,8,12,4,16,8,

%T 16,8,8,8,12,12,8,8,16,8,24,16,8,20,44,8,24,8,16,8,24,12,16,16,24,12,

%U 56,8,16,16,32,16,24,16,40,16,40,8,48,16,24,12,16,24,32,8,48,24

%N Number of Dirichlet characters chi modulo n generating the maximum Q(chi), where Q(chi) is the field generated by the values of chi.

%C Let psi = A002322 be the reduced totient function. Since Q(zeta_d) = Q(zeta_(2d)) for odd d, Q(chi) is the maximum when chi has order psi(n), or psi(n)/2 if psi(n) == 2 (mod 4). For any character chi', Q(chi') is a subfield of this maximum Q(chi) = Q(zeta_{psi(n)}).

%C For n >= 3, number of elements of order psi(n) in (Z/nZ)* if 4 | psi(n), and number of elements of order psi(n) or psi(n)/2 if psi(n) == 2 (mod 4).

%H Jianing Song, <a href="/A395683/b395683.txt">Table of n, a(n) for n = 1..10000</a>

%H Jianing Song, <a href="/A395473/a395473.txt">List of Q(chi) for characters chi modulo n <= 2048</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Dirichlet_character">Dirichlet character</a>.

%F For p prime, a(p) = EulerPhi(p-1) if p == 1 (mod 4), 2*EulerPhi(p-1) if p == 3 (mod 4).

%F For p prime and e >= 2, a(p^e), a(p^e) = EulerPhi(p-1)*(p-1)*p^(e-2) if p == 1 (mod 4), 2*EulerPhi(p-1)*p^(e-2) if p == 3 (mod 4); a(2^e) = 2^(e-2) for e >= 4.

%e If n is a divisor of 24, then Q(chi) = Q for every chi modulo n, so a(n) is just the number of Dirichlet characters, namely EulerPhi(n).

%e If p == 3 (mod 4) is prime, then Q(chi) reaches the maximum (namely Q(zeta_{(p-1)*p^(e-1)})) whenever chi has order (p-1)*p^(e-1) or (p-1)*p^(e-1)/2, so a(p^e) = 2*EulerPhi((p-1)*p^(e-1)).

%e If p == 1 (mod 4) is prime, then Q(chi) reaches the maximum (namely Q(zeta_{(p-1)*p^(e-1)})) only when chi has order (p-1)*p^(e-1), so a(p^e) = EulerPhi((p-1)*p^(e-1)).

%o (PARI) power_solution(invariant_factors, k) = vecprod(apply(x->gcd(x, k), invariant_factors)); \\ number of solutions to x^k = 1 in C_{k_1} X ... C_{k_r}

%o count_order(invariant_factors, k) = sumdiv(k, d, moebius(k/d)*power_solution(invariant_factors, d)); \\ number of elements of order k

%o a(n) = my(invariant_factors=znstar(n)[2], k=lcm(invariant_factors)); if(k%4==2, count_order(invariant_factors, k)+count_order(invariant_factors, k/2), count_order(invariant_factors, k));

%Y Cf. A002322, A396486, A111725.

%K nonn

%O 1,3

%A _Jianing Song_, Jun 03 2026