Find minimum number of generators for Z/nZ

[jackmell]

Is there a method to find the minimum number of generators $\big<a_1,a_2,\cdots,a_k\big>$ needed to generate $\mathbb{Z}_n^*$ such that $\mathop{\cap}\limits_{n=1}^k \big<a_n\big>=\{1\}$ other than by just looking for them and checking orders and products of group elements?

For example, what would be the minimum generator set for $\mathbb{Z}_{100!}^*$?

 

[micromass]

This is very difficult, even if $\mathbb{Z}_n^*$ is cyclic.

http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots

 

[micromass]

In your specific example, the best I can think of is the following. First prime decompose $100!$:

100! = 2^{97} \cdot 3^{48}\cdot 5^{24}\cdot 7^{15}\cdot 11^9\cdot 13^7\cdot 17^5\cdot 19^5\cdot 23^4\cdot 29^3\cdot 31^3\cdot 37^2\cdot 41^2\cdot 43^2\cdot 47^2\cdot 53\cdot 59\cdot 61\cdot 67\cdot 71\cdot 73\cdot 79\cdot 83\cdot 89\cdot 97
By the Chinese remainder theorem, we have
\mathbb{Z}^*_{100!} \cong \mathbb{Z}^*_{2^{97}}\times \mathbb{Z}^*_{3^{48}}\times \mathbb{Z}^*_{5^{24}}\times \mathbb{Z}^*_{7^{15}}\times \mathbb{Z}^*_{11^9}\times \mathbb{Z}^*_{13^7}\times \mathbb{Z}^*_{17^5}\times \mathbb{Z}^*_{19^5}\times \mathbb{Z}^*_{23^4}\times \mathbb{Z}^*_{29^3}\times \mathbb{Z}^*_{31^3}\times \mathbb{Z}^*_{37^2}\times \mathbb{Z}^*_{41^2}\times \mathbb{Z}^*_{43^2}\times \mathbb{Z}^*_{47^2}\times \mathbb{Z}^*_{53}\times \mathbb{Z}^*_{59}\times \mathbb{Z}^*_{61}\times \mathbb{Z}^*_{67}\times \mathbb{Z}^*_{71}\times \mathbb{Z}^*_{73}\times \mathbb{Z}^*_{79}\times \mathbb{Z}^*_{83}\times \mathbb{Z}^*_{89}\times \mathbb{Z}^*_{97}
(If you want the concrete generators, then you will have to find this isomorphism which means you'll need to have an algorithm which implements the Chinese remainder theorem).
The multiplicative group of a cyclic group of prime power is $\mathbb{Z}^*_{p^k}\cong \mathbb{Z}_{p^{k-1}(p-1)}$ (see the above post to find the generators of such a group). So the above factors are all cyclic. So you can find a minimal (generally not minimum) set of generators of cardinality $25$. Smaller sets might be possible.

 

[jackmell]

So you can find a minimal (generally not minimum) set of generators of cardinality $25$. Smaller sets might be possible.

Ok, I understand how 25 would do but I suspect there is no set $\big<a_1,a_2\cdots,a_{25}\big>$ that would generate the group such that $\mathop{\cap}\limits_{n=1}^{25} \big<a_n\big>=\{1\}$. I think we would need 26:

My conjecture:

Let $\mathbb{Z}_{n}^*\cong S_2\times S_{p_2}\times\cdot \times S_{p_n}$ where $S_p$ are the p-group expansions of $\mathbb{Z}_n^*$. Then the minimal number of generators $\big<a_1,a_2,\cdots,a_k\big>$ for the group such that $\mathop{\cap}\limits_{n=1}^{25} \big<a_n\big>=\{1\}$ is equal to the number of factors of $S_2$. In the case of $\mathbb{Z}_{100!}^*$, it's 26.

I was wondering if there is any way we could prove or disprove that though?

Edit:

After thinking about this, I may be wrong since it seems to me the intersection of the 25 generators micormass proposed above would also be the identity element. Not sure.