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

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,3

Comments

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}.

Links

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

Formula

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.

Example

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.

Prog

(PARI) 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); };

Crossrefs

Cf. A000010, A002322, A046072.

Cf. A033948 (positions of terms that are powers of 2).

Cf. A289626 (rgs-transform of this sequence).

Sequence in context: A278254 A091278 A127473 * A040004 A079611 A246763

Adjacent sequences: A289622 A289623 A289624 * A289626 A289627 A289628

Keyword

nonn

Author

Antti Karttunen, Jul 17 2017

Status

approved