A073103 -id:A073103 - cp's OEIS frontend

A357906 a(n) = log_2(A073103(n)).

0, 0, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2, 1, 3, 3, 2, 1, 1, 3, 2, 1, 1, 3, 2, 2, 1, 2, 2, 3, 1, 3, 2, 2, 3, 2, 2, 1, 3, 4, 2, 2, 1, 2, 3, 1, 1, 4, 1, 2, 3, 3, 2, 1, 3, 3, 2, 2, 1, 4, 2, 1, 2, 3, 4, 2, 1, 3, 2, 3, 1, 3, 2, 2, 3, 2, 2, 3, 1, 5, 1, 2, 1, 3, 4, 1, 3, 3, 2, 3, 3, 2, 2, 1, 3, 4, 2, 1, 2, 3

Offset: 1

Jianing Song, Oct 19 2022

			a(16) = 3 since x^4 == 1 (mod 16) has 2^3 = 8 solutions.

Jianing Song, Table of n, a(n) for n = 1..10000

Cf. A073103, A072273, A357905.

f[p_, e_] := If[Mod[p, 4] == 1, 2, 1]; f[2, e_] := Switch[e, 1, 0, 2, 1, 3, 2, , 3]; a[1] = 0; a[n] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 05 2023 *)

a(n)=my(f=factor(n)); sum(i=1, #f~, if(f[i, 1]==2, min(f[i, 2]-1, 3), if(f[i, 1]%4==1, 2, 1))) \\ after Charles R Greathouse IV's program for A073103

Additive with a(2) = 0, a(4) = 1, a(8) = 2, a(2^e) = 3, e >= 4; a(p^e) = 2 for p == 1 (mod 4), 1 for p == 3 (mod 4).

A060594 Number of solutions to x^2 == 1 (mod n), that is, square roots of unity modulo n.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 2, 4, 4, 2, 2, 2, 4, 4, 2, 2, 8, 2, 2, 2, 4, 2, 4, 2, 4, 4, 2, 4, 4, 2, 2, 4, 8, 2, 4, 2, 4, 4, 2, 2, 8, 2, 2, 4, 4, 2, 2, 4, 8, 4, 2, 2, 8, 2, 2, 4, 4, 4, 4, 2, 4, 4, 4, 2, 8, 2, 2, 4, 4, 4, 4, 2, 8, 2, 2, 2, 8, 4, 2, 4, 8, 2, 4, 4, 4, 4, 2, 4, 8, 2, 2, 4, 4, 2, 4, 2

Offset: 1

Jud McCranie, Apr 11 2001

Sum_{k=1..n} a(k) appears to be asymptotic to C*n*log(n) with C = 0.6... - Benoit Cloitre, Aug 19 2002
a(q) is the number of real characters modulo q. - Benoit Cloitre, Feb 02 2003
Also number of real Dirichlet characters modulo n and Sum_{k=1..n}a(k) is asymptotic to (6/Pi^2)*n*log(n). - Steven Finch, Feb 16 2006
Let P(n) be the product of the numbers less than and coprime to n. By theorem 59 in Nagell (which is Gauss's generalization of Wilson's theorem): for n > 2, P == (-1)^(a(n)/2) (mod n). - T. D. Noe, May 22 2009
Shadow transform of A005563. - Michel Marcus, Jun 06 2013
For n > 2, a(n) = 2 iff n is in A033948. - Max Alekseyev, Jan 07 2015
For n > 1, number of square numbers on the main diagonal of an (n-1) X (n-1) square array whose elements are the numbers from 1..n^2, listed in increasing order by rows. - Wesley Ivan Hurt, May 19 2021
a(n) is the number of linear Alexander quandles (Z/nZ, k) that are kei (equivalently, that have good involutions); see Ta, Prop. 5.6 and cf. A387317. - Luc Ta, Aug 26 2025

			The four numbers 1^2, 3^2, 5^2 and 7^2 are congruent to 1 modulo 8, so a(8) = 4.

Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. [From T. D. Noe, May 22 2009]
Gérald Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Cours spécialisé, 1995, Collection SMF, p. 260.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, pp. 196-197.

T. D. Noe, Table of n, a(n) for n = 1..1000
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
Keith Matthews, Solving the congruence x^2=a(mod m).
Emilia Mezzetti and Rosa Maria Miró-Roig, Togliatti systems and Galois coverings, arXiv preprint arXiv:1611.05620 [math.AG], 2016-2018. See Lemma 6.1.
John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type, Acta Cryst. (2009). A65, 156-163. [See Table 4].
N. J. A. Sloane, Transforms.
Lực Ta, Good involutions of twisted conjugation subquandles and Alexander quandles, arXiv:2508.16772 [math.GT], 2025.
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.

Cf. A000010, A005087, A033948, A046073, A073103 (x^4 == 1 (mod n)).
Cf. A001620, A306016.
Cf. A387317.

A060594 := proc(n)
   option remember;
   local a,b,c;
   if type(n,even) then
     a:= padic:-ordp(n,2);
     b:= 2^a;
     c:= n/b;
     min(b/2, 4) * procname(c)
   else
     2^nops(numtheory:-factorset(n))
   fi
end proc:
map(A060594, [$1 .. 100]); # Robert Israel, Jan 05 2015

a[n_] := Sum[ Boole[ Mod[k^2 , n] == 1], {k, 1, n}]; a[1] = 1; Table[a[n], {n, 1, 103}] (* Jean-François Alcover, Oct 21 2011 *)
a[n_] := Switch[Mod[n, 8], 2|6, 2^(PrimeNu[n]-1), 1|3|4|5|7, 2^PrimeNu[n], 0, 2^(PrimeNu[n]+1)]; Array[a, 103] (* Jean-François Alcover, Apr 09 2016 *)

PARI
```
a(n)=sum(i=1,n,if((i^2-1)%n,0,1))
```

a(n)=my(o=valuation(n,2));2^(omega(n>>o)+max(min(o-1,2),0)) \\ Charles R Greathouse IV, Jun 06 2013

a(n)=if(n<=2, 1, 2^#znstar(n)[3] ); \\ Joerg Arndt, Jan 06 2015

from sympy import primefactors
def a007814(n): return 1 + bin(n - 1).count('1') - bin(n).count('1')
def a(n):
    if n%2==0:
        A=a007814(n)
        b=2**A
        c=n//b
        return min(b//2, 4)*a(c)
    else: return 2**len(primefactors(n))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jul 18 2017, after the Maple program

from sympy import primefactors
def A060594(n): return (1<>(s:=(~n & n-1).bit_length()))))*(1 if n&1 else 1<Chai Wah Wu, Oct 26 2022

print([len(Integers(n).square_roots_of_one()) for n in range(1,100)]) # Ralf Stephan, Mar 30 2014

If n == 0 (mod 8), a(n) = 2^(A005087(n) + 2); if n == 4 (mod 8), a(n) = 2^(A005087(n) + 1); otherwise a(n) = 2^(A005087(n)). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 29 2001
a(n) = 2^omega(n)/2 if n == +/-2 (mod 8), a(n) = 2^omega(n) if n== +/-1, +/-3, 4 (mod 8), a(n) = 2*2^omega(n) if n == 0 (mod 8), where omega(n) = A001221(n). - Benoit Cloitre, Feb 02 2003
For n >= 2 A046073(n) * a(n) = A000010(n) = phi(n). This gives a formula for A046073(n) using the one in A060594(n). - Sharon Sela (sharonsela(AT)hotmail.com), Mar 09 2002
Multiplicative with a(2) = 1; a(2^2) = 2; a(2^e) = 4 for e > 2; a(q^e) = 2 for q an odd prime. - Eric M. Schmidt, Jul 09 2013
a(n) = 2^A046072(n) for n>2, in accordance with the above formulas by Ahmed Fares. - Geoffrey Critzer, Jan 05 2015
a(n) = Sum_{k=1..n} floor(sqrt(1+n*(k-1)))-floor(sqrt(n*(k-1))). - Wesley Ivan Hurt, May 19 2021
From Amiram Eldar, Dec 30 2022: (Start)
Dirichlet g.f.: (1-1/2^s+2/4^s)*zeta(s)^2/zeta(2*s).
Sum_{k=1..n} a(k) ~ (6/Pi^2)*n*(log(n) + 2*gamma - 1 - log(2)/2 - 2*zeta'(2)/zeta(2)), where gamma is Euler's constant (A001620). (End)

A060839 Number of solutions to x^3 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 3, 3, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 1, 3, 3, 3, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3, 1, 3, 3, 1, 1, 1, 3, 3, 9, 1, 3, 1, 3, 1, 1, 3, 1, 3, 3, 3, 1, 3, 3, 3, 3, 1, 3, 1, 1, 3, 1, 3, 1, 1, 1, 3, 9, 1, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3

Offset: 1

Ahmed Fares (ahmedfares(AT)my-deja.com), May 02 2001

Sum_{k=1..n} a(k) appears to be asymptotic to C*n*log(n) with C = 0.4... - Benoit Cloitre, Aug 19 2002 [C = (11/(6*Pi*sqrt(3))) * Product_{p prime == 1 (mod 3)} (1 - 2/(p*(p+1))) = 0.3170565167... (Finch and Sebah, 2006). - Amiram Eldar, Mar 26 2021]

			a(7) = 3 because the three solutions to x^3 == 1 (mod 7) are x = 1,2,4.

T. D. Noe, Table of n, a(n) for n = 1..1000
Steven Finch, Greg Martin and Pascal Sebah, Roots of unity and nullity modulo n, Proc. Amer. Math. Soc., Vol. 138, No. 8 (2010), pp. 2729-2743.
Steven Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A005088, A357905 (base-3 logarithm).
Number of solutions to x^k == 1 (mod n): A060594 (k=2), this sequence (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
Column 3 of A354057.

A060839 := proc(n)
    local a,pf,p,r;
    a := 1 ;
    for pf in ifactors(n)[2] do
        p := op(1,pf);
        r := op(2,pf);
        if p = 2 then
            ;
        elif p =3 then
            if r >= 2 then
                a := a*3 ;
            end if;
        else
            if modp(p,3) = 2 then
                ;
            else
                a := 3*a ;
            end if;
        end if;
    end do:
    a ;
end proc:
seq(A060839(n),n=1..40) ; # R. J. Mathar, Mar 02 2015

a[n_] := Sum[ If[ Mod[k^3-1, n] == 0, 1, 0], {k, 1, n}]; Table[ a[n], {n, 1, 105}](* Jean-François Alcover, Nov 14 2011, after PARI *)
f[p_, e_] := If[Mod[p, 3] == 1, 3, 1]; f[3, 1] = 1; f[3, e_] := 3; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

PARI
```
a(n)=sum(i=1,n,if((i^3-1)%n,0,1))
```

a(n)=my(f=factor(n)); prod(i=1, #f~, if(f[i, 1]==3, 3^min(f[i, 2]-1, 1), if(f[i, 1]%3==1, 3, 1))) \\ Jianing Song, Oct 21 2022

from math import prod
from sympy import factorint
def A060839(n): return prod(3 for p, e in factorint(n).items() if (p!=3 or e!=1) and p%3!=2) # Chai Wah Wu, Oct 19 2022

Let b(n) be the number of primes dividing n which are congruent to 1 (mod 3) (sequence A005088); then a(n) is 3^b(n) if n is not divisible by 9 and 3^(b(n) + 1) if n is divisible by 9.
Multiplicative with a(3) = 1, a(3^e) = 3, e >= 2, a(p^e) = 3 for primes p of the form 3k+1, a(p^e) = 1 for primes p of the form 3k+2. - David W. Wilson, May 22 2005 [Corrected by Jianing Song, Oct 21 2022]
If the multiplicative group of integers modulo n has (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then a(n) = Product_{i=1..r} gcd(3,k_r). - Jianing Song, Oct 21 2022

A319100 Number of solutions to x^6 == 1 (mod n).

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 6, 4, 6, 2, 2, 4, 6, 6, 4, 4, 2, 6, 6, 4, 12, 2, 2, 8, 2, 6, 6, 12, 2, 4, 6, 4, 4, 2, 12, 12, 6, 6, 12, 8, 2, 12, 6, 4, 12, 2, 2, 8, 6, 2, 4, 12, 2, 6, 4, 24, 12, 2, 2, 8, 6, 6, 36, 4, 12, 4, 6, 4, 4, 12, 2, 24, 6, 6, 4, 12, 12, 12, 6, 8, 6, 2

Offset: 1

Jianing Song, Sep 10 2018

All terms are 3-smooth. a(n) is even for n > 2. Those n such that a(n) = 2 are in A066501.

			Solutions to x^6 == 1 (mod 13): x == 1, 3, 4, 9, 10, 12 (mod 13).
Solutions to x^6 == 1 (mod 27): x == 1, 8, 10, 17, 19, 26 (mod 27) (x == 1, 8 (mod 9)).
Solutions to x^6 == 1 (mod 37): x == 1, 10, 11, 26, 27, 36 (mod 37).

Jianing Song, Table of n, a(n) for n = 1..10000
Steven Finch, Greg Martin and Pascal Sebah, Roots of unity and nullity modulo n, Proc. Amer. Math. Soc., Vol. 138, No. 8 (2010), pp. 2729-2743.

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), this sequence (k=6), A319101 (k=7), A247257 (k=8).
Cf. A046072, A066501, A088232, A293483, A000010.
Mobius transform gives A307381.

a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(6, Z[i]))

Multiplicative with a(2) = 1, a(4) = 2, a(2^e) = 4 for e >= 3; a(3) = 2, a(3^e) = 6 if e >= 2; for other primes p, a(p^e) = 6 if p == 1 (mod 6), a(p^e) = 2 if p == 5 (mod 6).
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(6, k_i).
a(n) = A060594(n)*A060839(n).
For n > 2, a(n) = A060839(n)*2^A046072(n).
a(n) = A060594(n) iff n is not divisible by 9 and no prime factor of n is congruent to 1 mod 6, that is, n in A088232.
a(n) = A000010(n)/A293483(n). - Jianing Song, Nov 10 2019
Sum_{k=1..n} a(k) ~ c * n * log(n)^3, where c = (1/Pi^4) * Product_{p prime == 1 (mod 6)} (1 - (12*p-4)/(p+1)^3) = 0.0075925601... (Finch et al., 2010). - Amiram Eldar, Mar 26 2021

A319099 Number of solutions to x^5 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 1, 1, 5, 1, 5, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 5, 5, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 5, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1

Offset: 1

Jianing Song, Sep 10 2018

All terms are powers of 5. Those n such that a(n) > 1 are in A066500.

			Solutions to x^5 == 1 (mod 11): x == 1, 3, 4, 5, 9 (mod 11).
Solutions to x^5 == 1 (mod 25): x == 1, 6, 11, 16, 21 (mod 25) (x == 1 (mod 5)).
Solutions to x^5 == 1 (mod 31): x == 1, 2, 4, 8, 16 (mod 31).

Jianing Song, Table of n, a(n) for n = 1..10000

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), this sequence (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
Cf. A030430, A066500, A293482, A000010.
Mobius transform gives A307380.

f[p_, e_] := If[Mod[p, 5] == 1, 5, 1]; f[5, 1] = 1; f[5, e_] := 5; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n)=my(Z=znstar(n)[2]); prod(i=1,#Z,gcd(5,Z[i]));

Multiplicative with a(5) = 1, a(5^e) = 5 if e >= 2; for other primes p, a(p^e) = 5 if p == 1 (mod 5), a(p^e) = 1 otherwise.
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(5, k_i).
a(n) = A000010(n)/A293482(n). - Jianing Song, Nov 10 2019

A319101 Number of solutions to x^7 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 7

Offset: 1

Jianing Song, Sep 10 2018

All terms are powers of 7. Those n such that a(n) > 1 are in A066502.

			Solutions to x^7 == 1 (mod 29): x == 1, 7, 16, 20, 23, 24, 25 (mod 29).
Solutions to x^7 == 1 (mod 43): x == 1, 4, 11, 16, 21, 35, 41 (mod 43).
Solutions to x^7 == 1 (mod 49): x == 1, 8, 15, 22, 29, 36, 43 (mod 49) (x == 1 (mod 7)).

Jianing Song, Table of n, a(n) for n = 1..10000

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), this sequence (k=7), A247257 (k=8).
Cf. A066502, A140444, A293484, A000010.
Mobius transform gives A307382.

f[p_, e_] := If[Mod[p, 7] == 1, 7, 1]; f[7, 1] = 1; f[7, e_] := 7; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(7, Z[i]))

Multiplicative with a(7) = 1, a(7^e) = 7 if e >= 2; for other primes p, a(p^e) = 7 if p == 1 (mod 7), a(p^e) = 1 otherwise.
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(7, k_i).
a(n) = A000010(n)/A293484(n). - Jianing Song, Nov 10 2019

A247257 The number of octic characters modulo n.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 2, 4, 2, 4, 2, 4, 4, 2, 8, 8, 8, 2, 2, 8, 4, 2, 2, 8, 4, 4, 2, 4, 4, 8, 2, 16, 4, 8, 8, 4, 4, 2, 8, 16, 8, 4, 2, 4, 8, 2, 2, 16, 2, 4, 16, 8, 4, 2, 8, 8, 4, 4, 2, 16, 4, 2, 4, 16, 16, 4, 2, 16, 4, 8, 2, 8, 8, 4, 8, 4, 4, 8, 2, 32

Offset: 1

R. J. Mathar, Mar 02 2015

Number of solutions to x^8 == 1 (mod n). - Jianing Song, Nov 10 2019

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Steven Finch, Quartic and octic characters modulo n, arXiv:0907.4894 [math.NT], 2009.

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), this sequence (k=8).

A247257 := proc(n)
    local a,pf,p,r;
    a := 1 ;
    for pf in ifactors(n)[2] do
        p := op(1,pf);
        r := op(2,pf);
        if p = 2 then
            if r >= 5 then
                a := a*16 ;
            else
                a := a*op(r,[1,2,4,8]) ;
            end if;
        elif modp(p,4) = 3 then
            a := a*2;
        elif modp(p,8) = 5 then
            a := a*4;
        elif modp(p,8) = 1 then
            a := a*8;
        else
            error
        end if;
    end do:
    a ;
end proc:

g[p_, e_] := Which[p==2, 2^Min[e-1, 4], Mod[p, 4]==3, 2, Mod[p, 8]==5, 4, True, 8];
a[1] = 1; a[n_] := Times @@ g @@@ FactorInteger[n];
Array[a, 80] (* Jean-François Alcover, Nov 26 2017, after Charles R Greathouse IV *)

g(p,e)=if(p==2, 2^min(e-1,4), if(p%4==3, 2, if(p%8==5, 4, 8)))
a(n)=my(f=factor(n)); prod(i=1,#f~, g(f[i,1],f[i,2])) \\ Charles R Greathouse IV, Mar 02 2015

Multiplicative with a(p^e) = p^min(e-1, 4) if p = 2, gcd(8, p-1) if p > 2. - Jianing Song, Nov 10 2019

A160499 Number of quartic primitive Dirichlet characters modulo n.

Original entry on oeis.org

1, 0, 1, 1, 3, 0, 1, 2, 0, 0, 1, 1, 3, 0, 3, 4, 3, 0, 1, 3, 1, 0, 1, 2, 0, 0, 0, 1, 3, 0, 1, 0, 1, 0, 3, 0, 3, 0, 3, 6, 3, 0, 1, 1, 0, 0, 1, 4, 0, 0, 3, 3, 3, 0, 3, 2, 1, 0, 1, 3, 3, 0, 0, 0, 9, 0, 1, 3, 1, 0, 1, 0, 3, 0, 0, 1, 1, 0, 1, 12, 0

Offset: 1

Steven Finch, May 15 2009

Also called biquadratic primitive Dirichlet characters.
Primitive Dirichlet characters of both order 2 & order 4 are included.
a(n) is the number of primitive Dirichlet characters modulo n such that all entries are 0 or a fourth-power root of unity (1, i, -1 and -i). - Jianing Song, Feb 27 2019
Mobius transform of A073103. - Jianing Song, Mar 02 2019

			From _Jianing Song_, Mar 02 2019: (Start)
For n = 5, the 3 quartic primitive Dirichlet characters modulo n are [0, 1, -1, -1, 1], [0, 1, i, -i, -1] and [0, 1, -i, i, -1], so a(5) = 3.
For n = 16, the 4 quartic primitive Dirichlet characters modulo n are [0, 1, 0, i, 0, i, 0, 1, 0, -1, 0, -i, 0, -i, 0, -1], [0, 1, 0, -i, 0, -i, 0, 1, 0, -1, 0, i, 0, i, 0, -1], [0, 1, 0, i, 0, -i, 0, -1, 0, -1, 0, -i, 0, i, 0, 1] and [0, 1, 0, -i, 0, i, 0, -1, 0, -1, 0, i, 0, -i, 0, 1], so a(16) = 4. (End)

Jianing Song, Table of n, a(n) for n = 1..10000
Steven R. Finch, Cubic and quartic characters.
Steven R. Finch, Cubic and quartic characters.
Steven R. Finch, Quartic and Octic Characters Modulo n, arXiv:0907.4894 [math.NT], 2016.

Cf. A114643 (number of quadratic primitive Dirichlet characters modulo n), A160498 (number of cubic primitive Dirichlet characters modulo n).
Cf. A073103 (number of solutions to x^4 == 1 (mod n)).
Cf. A064533.

f[n_] := Sum[If[Mod[k^4 - 1, n] == 0, 1, 0], {k, 1, n}]; a[n_] := Sum[ MoebiusMu[n/d]*f[d], {d, Divisors[n]}]; Table[a[n], {n, 2, 81}] (* Jean-François Alcover, Jun 19 2013 *)
f[2, e_] := Which[e == 1, 0, e == 2, 1, e == 3, 2, e == 4, 4, e >= 5, 0]; f[p_, 1] := If[Mod[p, 4] == 1, 3, 1]; f[p_, e_] := 0; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 16 2020 *)

a(n)=sum(d=1, n, if(n%d==0, moebius(n/d)*sum(i=1, d, if((i^4-1)%d, 0, 1)), 0)) \\ Steven Finch, Jun 09 2009

Multiplicative with a(4) = 1, a(8) = 2, a(16) = 4, a(2^e) = 0 for e = 1 or e >= 5; for odd primes p, a(p) = 3 if p == 1 (mod 4) and 1 if p == 3 (mod 4), a(p^e) = 0 for e >= 2. - Jianing Song, Mar 02 2019

Sum_{k=1..n} a(k) ~ c * n * log(n), where c = (7/(16*Pi*K^2)) * Product_{primes p == 1 (mod 4)} (1 - (5*p-3)/(p^2*(p+1))) = 0.1908767211685284480112237..., and K is the Landau-Ramanujan constant (A064533). - Amiram Eldar, Sep 16 2020

a(1) = 1 prepended by Jianing Song, Feb 27 2019

A250207 The number of quartic terms in the multiplicative group modulo n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 5, 1, 3, 3, 1, 1, 4, 3, 9, 1, 3, 5, 11, 1, 5, 3, 9, 3, 7, 1, 15, 2, 5, 4, 3, 3, 9, 9, 3, 1, 10, 3, 21, 5, 3, 11, 23, 1, 21, 5, 4, 3, 13, 9, 5, 3, 9, 7, 29, 1, 15, 15, 9, 4, 3, 5, 33, 4, 11, 3, 35, 3, 18, 9, 5, 9, 15, 3, 39, 1

Offset: 1

R. J. Mathar, Mar 02 2015

In the character table of the multiplicative group modulo n there are phi(n) different characters. [This is made explicit for example by the number of rows in arXiv:1008.2547.] The set of the fourth powers of the characters in all representations has some cardinality, which defines the sequence.

			For n <= 6, the set of all characters in all representations consists of a subset of +1, -1, +i or -i. Their fourth powers are all +1, a single value, so a(n)=1 then.
For n=7, the set of characters is 1, -1, +-1/2 +- sqrt(3)*i/2, so their fourth powers are 1 or -1/2 +- sqrt(3)*i/2, which are three different values, so a(7)=3.
For n=11, the fourth powers of the characters may be 1, exp(+-2*i*Pi/5) or exp(+-4*i*Pi/5), which are 5 different values.

Antti Karttunen, Table of n, a(n) for n = 1..10000
R. J. Mathar, Size of the Set of Residues of Integer Powers of Fixed Exponent, (2017).
R. J. Mathar, Table of Dirichlet L-series and prime zeta modulo functions for small moduli, arXiv:1008.2547 [math.NT], 2010.
Wikipedia, Dirichlet character.

Cf. A046073, A087692, A052273, A293482 - A293485.

A250207 := proc(n)
    numtheory[phi](n)/A073103(n) ;
end proc:

a[n_] := EulerPhi[n]/Count[Range[0, n-1]^4 - 1, k_ /; Divisible[k, n]];
Array[a, 80] (* Jean-François Alcover, Nov 20 2017 *)
f[p_, e_] := (p - 1)*p^(e - 1)/If[Mod[p, 4] == 1, 4, 2]; f[2, e_] := If[e <= 3, 1, 2^(e - 4)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n)=my(f=factor(n)); prod(i=1,#f~, if(f[i,1]==2, 2^max(0,f[i,2]-4), f[i,1]^(f[i,2]-1)*(f[i,1]-1)/if(f[i,1]%4==1,4,2))) \\ Charles R Greathouse IV, Mar 02 2015

a(n) = A000010(n)/A073103(n).

Multiplicative with a(2^e) = 1 for e<=3; a(2^e) = 2^(e-4) for e>=4; a(p^e) = p^(e-1)*(p-1)/4 for e>=1 and p == 1 (mod 4); a(p^e) = p^(e-1)*(p-1)/2 for e>=1 and p == 3 (mod 4). (Derived from A073103.) - R. J. Mathar, Oct 13 2017

A354057 Square array read by ascending antidiagonals: T(n,k) is the number of solutions to x^k == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 4, 3, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 3, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 6, 1, 4, 1, 2, 1, 1, 1, 4, 1, 4, 1, 4, 1, 2, 1, 2, 1, 1, 1

Offset: 1

Jianing Song, May 16 2022

Row n and Row n' are the same if and only if (Z/nZ)* = (Z/n'Z)*, where (Z/nZ)* is the multiplicative group of integers modulo n.
Given n, T(n,k) only depends on gcd(k,psi(n)). For the truncated version see A354060.
Each column is multiplicative.

			  n/k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   1   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   3   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   4   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   5   1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4
   6   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   7   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
   8   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
   9   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  10   1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4
  11   1  2  1  2  5  2  1  2  1 10  1  2  1  2  5  2  1  2  1 10
  12   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
  13   1  2  3  4  1  6  1  4  3  2  1 12  1  2  3  4  1  6  1  4
  14   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  15   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
  16   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
  17   1  2  1  4  1  2  1  8  1  2  1  4  1  2  1 16  1  2  1  4
  18   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  19   1  2  3  2  1  6  1  2  9  2  1  6  1  2  3  2  1 18  1  2
  20   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8

Jianing Song, Table of n, a(n) for n = 1..5050 (the first 100 ascending diagonals)

k-th column: A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
Applying Moebius transform to the rows gives A354059.
Applying Moebius transform to the columns gives A354058.
Cf. A327924.

T(n,k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]))

If (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then T(n,k) = Product_{i=1..r} gcd(k,k_r).
T(p^e,k) = gcd((p-1)*p^(e-1),k) for odd primes p. T(2,k) = 1, T(2^e,k) = 2*gcd(2^(e-2),k) if k is even and 1 if k is odd.
A327924(n,k) = Sum_{q|n} T(n,k) * (Sum_{s|n/q} mu(s)/phi(s*q)).

cp's OEIS Frontend

A357906 a(n) = log_2(A073103(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A060594 Number of solutions to x^2 == 1 (mod n), that is, square roots of unity modulo n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Sage

Formula

A060839 Number of solutions to x^3 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A319100 Number of solutions to x^6 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A319099 Number of solutions to x^5 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A319101 Number of solutions to x^7 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI