A046072 -id:A046072 - cp's OEIS frontend

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

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)

A046073 Number of squares in multiplicative group modulo n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, 3, 2, 2, 8, 3, 9, 2, 3, 5, 11, 1, 10, 6, 9, 3, 14, 2, 15, 4, 5, 8, 6, 3, 18, 9, 6, 2, 20, 3, 21, 5, 6, 11, 23, 2, 21, 10, 8, 6, 26, 9, 10, 3, 9, 14, 29, 2, 30, 15, 9, 8, 12, 5, 33, 8, 11, 6, 35, 3, 36, 18, 10, 9, 15, 6, 39, 4, 27, 20, 41, 3, 16, 21

Offset: 1

Eric W. Weisstein

a(n) is the number of different diagonal elements in Cayley table for multiplicative group modulo n. But the fact that the same number of different elements are on the diagonal of the Cayley table does not mean in every case that these groups are isomorphic. - Artur Jasinski, Jul 03 2010

The number of quadratic residues modulo n that are coprime to n. These residues are listed in A096103. - Peter Munn, Mar 10 2021

Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 95, 1993.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Steven R. Finch and Pascal Sebah, Square and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Eric Weisstein's World of Mathematics, Quadratic Residue.

Cf. A046072, A007735, A060594, A000010, A087692, A000224.
Row lengths of A096103.
Positions of ones: A018253.

F:= n -> nops({seq}(`if`(igcd(t,n)=1,t^2 mod n,NULL), t=1..floor(n/2))):
1, seq(F(n), n=2..100); # Robert Israel, Jan 04 2015
# 2nd program
A046073 := proc(n)
    local a,p,e,pf;
    a := 1;
    for pf in ifactors(n)[2] do
        p := op(1,pf) ;
        e := op(2,pf) ;
        if p = 2 then
            a := a*p^max(e-3,0) ;
        else
            a := a*(p-1)/2*p^(e-1) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Oct 03 2016

Table[EulerPhi[n]/Sum[Boole[Mod[k^2, n] == 1] + Boole[n == 1], {k, n}], {n, 86}] (* or *)
Table[Apply[Times, FactorInteger[n] /. {p_, e_} /; p > 0 :> Which[p == 1, 1, p == 2, 2^Max[e - 3, 0], True, (p - 1) p^(e - 1)/2]], {n, 86}] (* Michael De Vlieger, Jul 18 2017 *)

A060594(n) = if(n<=2, 1, 2^#znstar(n)[3]); \\ This function from Joerg Arndt, Jan 06 2015
A046073(n) = eulerphi(n)/A060594(n); \\ Antti Karttunen, Jul 17 2017, after Sharon Sela's Mar 09 2002 formula.

A046073(n)=if(n>4,(n=znstar(n))[1]>>#n[3],1) \\ Avoids duplicate computation of phi(n). - M. F. Hasler, Nov 27 2017, typo fixed Mar 11 2021

from sympy import factorint, prod
def a(n): return 1 if n==1 else prod([2**max(e - 3, 0) if p==2 else (p - 1)*p**(e - 1)//2 for p, e in factorint(n).items()])
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 17 2017

(define (A046073 n) (cond ((= 1 n) n) ((even? n) (* (A000079 (max (- (A007814 n) 3) 0)) (A046073 (A028234 n)))) (else (* (/ 1 2) (- (A020639 n) 1) (/ (A028233 n) (A020639 n)) (A046073 (A028234 n)))))) ;; Antti Karttunen, Jul 17 2017, after the given multiplicative formula.

a(n) * A060594(n) = A000010(n) = phi(n) (This gives a formula for a(n) using the one in A060594(n) ). - Sharon Sela (sharonsela(AT)hotmail.com), Mar 09 2002
Multiplicative with a(2^e) = 2^max(e-3,0), a(p^e) = (p-1)*p^(e-1)/2 for p an odd prime.
Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (43/(80*sqrt(Pi))) * Product_{p prime} (1+1/(2*p))*sqrt(1-1/p) = 0.24627260085060864229... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022

Edited and verified by Franklin T. Adams-Watters, Nov 07 2006

A289625 a(n) = prime factorization encoding of the structure of the multiplicative group of integers modulo n.

Original entry on oeis.org

1, 1, 4, 4, 16, 4, 64, 36, 64, 16, 1024, 36, 4096, 64, 144, 144, 65536, 64, 262144, 144, 576, 1024, 4194304, 900, 1048576, 4096, 262144, 576, 268435456, 144, 1073741824, 2304, 9216, 65536, 36864, 576, 68719476736, 262144, 36864, 3600, 1099511627776, 576, 4398046511104, 9216, 36864, 4194304, 70368744177664, 3600, 4398046511104, 1048576, 589824, 36864

Offset: 1

Antti Karttunen, Jul 17 2017

nonn

Here multiplicative group of integers modulo n is decomposed as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i > j, like PARI-function znstar does. a(n) is then 2^{k_1} * 3^{k_2} * 5^{k_3} * ... * prime(m)^{k_m}.

			For n=5, the multiplicative group modulo 5 is isomorphic to C_4, which does not factorize to smaller subgroups, thus a(5) = 2^4 = 16.
For n=8, the multiplicative group modulo 8 is isomorphic to C_2 x C_2, thus a(8) = 2^2 * 3^2 = 36.
For n=15, the multiplicative group modulo 15 is isomorphic to C_4 x C_2, thus a(15) = 2^4 * 3^2 = 144.

Antti Karttunen, Table of n, a(n) for n = 1..1024
The PARI group, Catalogue of GP/PARI Functions: Arithmetic functions, function znstar
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Wikipedia, Multiplicative group of integers modulo n

Cf. A000010, A002322, A046072.
Cf. A033948 (positions of terms that are powers of 2).
Cf. A289626 (rgs-transform of this sequence).

A289625(n) = { my(m=1,p=2,v=znstar(n)[2]); for(i=1,length(v),m *= p^v[i]; p = nextprime(p+1)); (m); };

A005361(a(n)) = A000010(n).
A072411(a(n)) = A002322(n).
A007814(a(n)) = A002322(n) for n > 2.
A001221(a(n)) = A046072(n) for n > 2.

A289626 Restricted growth sequence transform of A289625, related to the structure of multiplicative group of integers modulo n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 4, 5, 4, 3, 6, 5, 7, 4, 8, 8, 9, 4, 10, 8, 11, 6, 12, 13, 14, 7, 10, 11, 15, 8, 16, 17, 18, 9, 19, 11, 20, 10, 19, 21, 22, 11, 23, 18, 19, 12, 24, 21, 23, 14, 25, 19, 26, 10, 27, 28, 29, 15, 30, 21, 31, 16, 32, 25, 33, 18, 34, 25, 35, 19, 36, 28, 37, 20, 27, 29, 38, 19, 39, 40, 41, 22, 42, 28, 43, 23, 44, 45, 46, 19, 47, 35, 38, 24, 48, 49

Offset: 1

Antti Karttunen, Jul 18 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A289625, A101296.

Cf. A000010, A002322, A034380, A046072, A289624 (some of the matching sequences).

rgs_transform(invec) = { my(occurrences = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(occurrences,invec[i]), my(pp = mapget(occurrences, invec[i])); outvec[i] = outvec[pp] , mapput(occurrences,invec[i],i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A289625(n) = { my(m=1,p=2,v=znstar(n)[2]); for(i=1,length(v),m *= p^v[i]; p = nextprime(p+1)); (m); };
write_to_bfile(1,rgs_transform(vector(16384,n,A289625(n))),"b289626_upto16384.txt");

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

A102476 Least modulus with 2^n square roots of 1.

Original entry on oeis.org

1, 3, 8, 24, 120, 840, 9240, 120120, 2042040, 38798760, 892371480, 25878772920, 802241960520, 29682952539240, 1217001054108840, 52331045326680120, 2459559130353965640, 130356633908760178920, 7691041400616850556280

Offset: 0

David W. Wilson, Jan 10 2005

The number of square roots of 1 in any modulus is a power of 2.
Another way of expressing the same:  These are also the record setting values of m for the number of solutions to "m*k+1 is a square", for some k, 0<=k<=m. There is 1 solution for a(0)=m=1, and for m = a(n), n>0, there is the first occurrence of 2^n solutions. Compare with A006278.  - Richard R. Forberg, Mar 18 2016
Also a(n) is the least k such that the proportion of squares in a reduced residue system modulo n is 1/2^n, i.e. A046073(k)/A000010(k) = 1/2^n. - Jianing Song, Nov 12 2019
From Jianing Song, Oct 18 2021: (Start)
a(n) is the smallest k such that rank((Z/kZ)*) = n. The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G. In particular, rank((Z/kZ)*) = 0 if k <= 2 and A046072(k) otherwise.
The number of coprime squares modulo a(n) is given by A046073(a(n)) = A323739(n-1) for n >= 2. (End)

			a(3) = 24 because 24 is the least modulus with 2^3 square roots of 1, namely 1,5,7,11,13,17,19,23.

Harvey P. Dale, Table of n, a(n) for n = 0..351

Cf. A060594, A002110, A006278, A046072, A046073, A272590, A323739.

{1, 3}~Join~Table[4 Product[Prime[k], {k, n}], {n, 17}] (* Michael De Vlieger, Mar 27 2016 *)
nxt[{a_, p_}] := {a*NextPrime[p], NextPrime[p]}; Join[{1,3},NestList[nxt,{8,2},20][[All,1]]] (* or *) Join[{1,3},4*FoldList[ Times, Prime[ Range[ 21]]]](* Harvey P. Dale, Dec 18 2016 *)

a(n) = if(n<=1, [1,3][n+1], 4*factorback(primes(n-1))) \\ Jianing Song, Oct 19 2021, following David A. Corneth's program for A002110

a(n) = 4(prime(n-1))# = 4*A002110(n-1) for n >= 2. Least k with A060594(k) = 2^n.

A272592 Numbers n such that the multiplicative group modulo n is the direct product of 2 cyclic groups.

Original entry on oeis.org

8, 12, 15, 16, 20, 21, 28, 30, 32, 33, 35, 36, 39, 42, 44, 45, 51, 52, 55, 57, 63, 64, 65, 66, 68, 69, 70, 75, 76, 77, 78, 85, 87, 90, 91, 92, 93, 95, 99, 100, 102, 108, 110, 111, 114, 115, 116, 117, 119, 123, 124, 126, 128, 129, 130, 133, 135, 138, 141, 143, 145, 147, 148, 150, 153, 154, 155, 159, 161

Offset: 1

Joerg Arndt, May 03 2016

nonn

Numbers n such that A046072(n) = 2.

Numbers are of the form p^e*q^f, 2*p^e*q^f, 4p^e, or 2^(e+2) where p and q are distinct odd primes and e,f >= 1. - Charles R Greathouse IV, Jan 09 2022

Cf. A046072.
Supersequence of A225375.
Direct product of k groups: A033948 (k=1), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[200], A046072[#] == 2&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1,10^3, my(t=#(znstar(n)[2]));if(t==2,print1(n,", ")));

A272593 Numbers n such that the multiplicative group modulo n is the direct product of 3 cyclic groups.

Original entry on oeis.org

24, 40, 48, 56, 60, 72, 80, 84, 88, 96, 104, 105, 112, 132, 136, 140, 144, 152, 156, 160, 165, 176, 180, 184, 192, 195, 200, 204, 208, 210, 216, 220, 224, 228, 231, 232, 248, 252, 255, 260, 272, 273, 276, 285, 288, 296, 300, 304, 308, 315, 320, 328, 330, 340, 344, 345, 348, 352, 357, 364, 368, 372, 376, 380

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 3.

Cf. A046072.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[400], A046072[#] == 3&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 10^3, my(t=#(znstar(n)[2])); if(t==3, print1(n, ", ")));

A272594 Numbers n such that the multiplicative group modulo n is the direct product of 4 cyclic groups.

Original entry on oeis.org

120, 168, 240, 264, 280, 312, 336, 360, 408, 420, 440, 456, 480, 504, 520, 528, 552, 560, 600, 616, 624, 660, 672, 680, 696, 720, 728, 744, 760, 780, 792, 816, 880, 888, 912, 920, 924, 936, 952, 960, 984, 1008, 1020, 1032, 1040, 1056, 1064, 1080, 1092, 1104, 1120, 1128, 1140, 1144, 1155, 1160, 1176, 1200

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 4.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[1200], A046072[#] == 4&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 3*10^3, my(t=#(znstar(n)[2])); if(t==4, print1(n, ", ")));

A272595 Numbers n such that the multiplicative group modulo n is the direct product of 5 cyclic groups.

Original entry on oeis.org

840, 1320, 1560, 1680, 1848, 2040, 2184, 2280, 2520, 2640, 2760, 2856, 3080, 3120, 3192, 3360, 3432, 3480, 3640, 3696, 3720, 3864, 3960, 4080, 4200, 4368, 4440, 4488, 4560, 4620, 4680, 4760, 4872, 4920, 5016, 5040, 5160, 5208, 5280, 5304, 5320, 5460, 5520, 5544, 5640, 5712, 5720, 5880, 5928, 6072, 6120

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 5.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[10^4], A046072[#] == 5&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 10^4, my(t=#(znstar(n)[2])); if(t==5, print1(n, ", ")));

cp's OEIS Frontend

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

A046073 Number of squares in multiplicative group modulo n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

Extensions

A289625 a(n) = prime factorization encoding of the structure of the multiplicative group of integers modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A289626 Restricted growth sequence transform of A289625, related to the structure of multiplicative group of integers modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A102476 Least modulus with 2^n square roots of 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A272592 Numbers n such that the multiplicative group modulo n is the direct product of 2 cyclic groups.