|
%I #20 Mar 10 2021 01:27:33
%S 1,1,1,1,1,1,1,3,1,1,1,3,1,1,4,4,1,1,1,4,6,1,1,28,1,1,1,6,1,4,1,4,6,1,
%T 8,6,1,1,8,48,1,6,1,6,8,1,1,48,1,1,4,8,1,1,8,84,6,1,1,48,1,1,36,4,24,
%U 6,1,4,6,8,1,84,1,1,8,6,12,8,1,192,1,1,1,84,16,1,8,84,1,8
%N Number of ways, up to order, of decomposing (Z/nZ)* as the internal direct product of r cyclic subgroups, where r = rank((Z/nZ)*).
%C In general, let G be a finite abelian group and r = rank(G), let s be the number of arrays (k_1, k_2, ..., k_r) such that G = C_(k_1) X C_(k_2) X ... X C_(k_r). We can see from A302257 that:
%C (a) Given (k'_1, k'_2, ..., k'_r) such that G = C_(k'_1) X C_(k'_2) X ... X C_(k'_r), the number of arrays (a_1, a_2, ..., a_r) such that G = <a_1> X <a_2> X ... <a_r> and that ord(a_i) = k'_i is |Aut(G)|, where <a> is the subgroup of G generated by a. This is because if one group of such (a_1, a_2, ..., a_r) is found, all the others can be found by group automorphism. As a result, the number of sets {a_1, a_2, ..., a_r} such that G = <a_1> X <a_2> X ... <a_r> is |Aut(G)|*s/r!. As (k'_1, k'_2, ..., k'_r) runs through all the s possible choices, each array (a_1, a_2, ..., a_r) such that G = <a_1> X <a_2> X ... <a_r> occurs exactly once, giving a total of |Aut(G)|*s arrays. But the elements in a set are unordered, so the number of sets is |Aut(G)|*s/r!;
%C (b) Let M = Product_{i=1..r} phi(k_i), then the number of sets {H_1, H_2, ..., H_r} such that G = H_1 X H_2 X ... X H_r is (|Aut(G)|*s/r!)/M. Given {H_1, H_2, ..., H_r} such that G = H_1 X H_2 X ... X H_r, there are phi(|H_i|) ways to choose a generator of H_i, that is, there are Product_{i=1..r} phi(|H_i|) sets {a_1, a_2, ..., a_r} such that <a_i> = H_i. From (a), the total number of sets {a_1, a_2, ..., a_r} as {H_1, H_2, ..., H_r} runs through all possible choices is |Aut(G)|*s/r!. Note that Product_{i=1..r} phi(|H_i|) is always equal to M regardless of the choice of {H_1, H_2, ..., H_r}. That is to say, each set of cyclic subgroups {H_1, H_2, ..., H_r} corresponds to M sets of generators {a_1, a_2, ..., a_r}. Thus, the number of sets {H_1, H_2, ..., H_r} is (|Aut(G)|*s/r!)/M.
%H Jianing Song, <a href="/A327791/b327791.txt">Table of n, a(n) for n = 1..10000</a>
%H Jianing Song, <a href="/A327791/a327791.txt">The full PARI program</a>
%H The Group Properties Wiki, <a href="https://groupprops.subwiki.org/wiki/Internal_direct_product">Internal direct product</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>
%F a(n) = A302257(n)/A327790(n).
%e n = 8: (Z/8Z)* = {1, 3} X {1, 5} = {1, 3} X {1, 7} = {1, 5} X {1, 7}, so a(8) = 3;
%e n = 16: (Z/16Z)* = {1, 3, 9, 11} X {1, 7} = {1, 3, 9, 11} X {1, 15} = {1, 5, 9, 13} X {1, 7} = {1, 5, 9, 13} X {1, 15}, so a(16) = 4;
%e n = 35: (Z/35Z)* = {1, 2, 4, 8, 9, 11, 16, 18, 22, 23, 29, 32} X {1, 6} = {1, 2, 4, 8, 9, 11, 16, 18, 22, 23, 29, 32} X {1, 34} = {1, 3, 4, 9, 11, 12, 13, 16, 17, 27, 29, 33} X {1, 6} = {1, 3, 4, 9, 11, 12, 13, 16, 17, 27, 29, 33} X {1, 34} = {1, 8, 22, 29} X {1, 11, 16, 19, 24, 34} = {1, 8, 22, 29} X {1, 6, 11, 16, 26, 31} = {1, 13, 27, 29} X {1, 11, 16, 19, 24, 34} = {1, 13, 27, 29} X {1, 6, 11, 16, 26, 31}, so a(35) = 8.
%o (PARI) a(n) = A302257(n)/A327790(n) \\ See A302257 and A327790 for their programs [See the link section for the full program. - _Jianing Song_, Mar 08 2021]
%Y Cf. A302257, A327790.
%K nonn
%O 1,8
%A _Jianing Song_, Sep 25 2019
|
