This is a question about the structure theory of finite abelian groups. You are asking for the minimum size of generators for the multiplicative group $\Bbb{Z}_n^*$ of residue classes coprime to $n$. As is often the case the Chinese remainder theorem is your friend. If $$ n=\prod_{j=1}^kp_j^{a_j}\qquad(*) $$ is the prime factorization of $n$, then CRT tells us that $$ \Bbb{Z}_n^*\cong\prod_j\Bbb{Z}_{p_j^{a_j}}. $$ Furthermore, it is well known that for $n\ge2$ $$ \Bbb{Z}_{2^n}\cong C_2\times C_{2^{n-2}} $$ with the former factor generated by $-1$ and the latter by $5$. For all the odd primes $p$, the situation is simpler, and $$ \Bbb{Z}_{p^n}\cong C_{p^{n-1}(p-1)} $$ is cyclic (in other words, there exists a primitive root modulo a power of an odd prime). Putting these together gives us a way of writing $\Bbb{Z}_n^*$ as a direct product of cyclic groups.

To answer the question about the minimal number of generators we need an elementary result from the structure theory of finite abelian groups. Namely, that a finite abelian group $G$ can be written as a direct product of cyclic groups $$ G=C_{d_1}\times C_{d_2}\times \cdots\times C_{d_k}\qquad(**) $$ in such a way that $d_i\mid d_{i+1}$ for all $i=1,2,\ldots,k-1$. The numbers $d_i$ are known as invariant factors of $G$ and, as the name suggests, they are uniquely determined by the group $G$.

Without loss of generality we can assume that $d_1>1$. Given this, it follows that

The minimum number of generators for $G$ is equal to $k$.

A proof follows from $(**)$ easily. Obviously a set of generators of the factors, one for each, generates all of $G$. So $k$ generators suffices. OTOH, if $p$ is a prime divisor of $d_1$, then $G$ has $C_p^k$ as a quotient group. That is, a $k$-dimensional vector space over the field $\Bbb{Z}_p$. That group requires a minimum of $k$ generators (=basis vectors) by linear algebra. Hence, so does $G$.

How does this apply? The method for finding the invariant factors is algorithmic (and at least many instances have been covered on the site already). We can actually easily describe the number of invariant factors divisible by a fixed prime $q$ as follows.

Given $n$, the decomposition $(*)$, and a prime $q$, the number of invariant factors divisible by $q$, call it $\ell(n,q)$ is gotten as the following sum: $$\ell(n,q)=\sum_j e_(p_j,q),$$ where $$ e(p,q)= \begin{cases} 2,\ &\text{if $p=q=2$ and $8\mid n$},\\ 1,\ &\text{if $p=q=2$, $4\mid n$, but $8\nmid n$},\\ 1,\ &\text{if $p=q>2$, and $p^2\nmid n$},\\ 1,\ &\text{if $p\neq q$, and $q\mid p-1$},\\ 0,\ &\text{in all the other cases.} \end{cases} $$ This follows by a study of the orders of all those cyclic factors. Again, $\Bbb{Z}_n^*$ will have a quotient group isomorphic to $C_q^{\ell(n,q)}$.

Then the final answer is:

The minimum number of generators of $\Bbb{Z}_n^*$ is the maximum of the numbers $\ell(n,q)$ with $q$ ranging over the primes.

Upon reading Greg Martin's fine answer I realized that $\ell(n,2)$ is always the maximum of the numbers $\ell(n,q)$. Therefore it suffices to calculate $\ell(n,2)$, and the answer is what Greg wrote.

This is a question about the structure theory of finite abelian groups. You are asking for the minimum size of generators for the multiplicative group $\Bbb{Z}_n^*$ of residue classes coprime to $n$. As is often the case the Chinese remainder theorem is your friend. If $$ n=\prod_{j=1}^kp_j^{a_j}\qquad(*) $$ is the prime factorization of $n$, then CRT tells us that $$ \Bbb{Z}_n^*\cong\prod_j\Bbb{Z}_{p_j^{a_j}}. $$ Furthermore, it is well known that for $n\ge2$ $$ \Bbb{Z}_{2^n}^*\cong C_2\times C_{2^{n-2}} $$ with the former factor generated by $-1$ and the latter by $5$. For all the odd primes $p$, the situation is simpler, and $$ \Bbb{Z}_{p^n}^*\cong C_{p^{n-1}(p-1)} $$ is cyclic (in other words, there exists a primitive root modulo a power of an odd prime). Putting these together gives us a way of writing $\Bbb{Z}_n^*$ as a direct product of cyclic groups.

To answer the question about the minimal number of generators we need an elementary result from the structure theory of finite abelian groups. Namely, that a finite abelian group $G$ can be written as a direct product of cyclic groups $$ G=C_{d_1}\times C_{d_2}\times \cdots\times C_{d_k}\qquad(**) $$ in such a way that $d_i\mid d_{i+1}$ for all $i=1,2,\ldots,k-1$. The numbers $d_i$ are known as invariant factors of $G$ and, as the name suggests, they are uniquely determined by the group $G$.

Without loss of generality we can assume that $d_1>1$. Given this, it follows that

The minimum number of generators for $G$ is equal to $k$.

A proof follows from $(**)$ easily. Obviously a set of generators of the factors, one for each, generates all of $G$. So $k$ generators suffices. OTOH, if $p$ is a prime divisor of $d_1$, then $G$ has $C_p^k$ as a quotient group. That is, a $k$-dimensional vector space over the field $\Bbb{Z}_p$. That group requires a minimum of $k$ generators (=basis vectors) by linear algebra. Hence, so does $G$.

How does this apply? The method for finding the invariant factors is algorithmic (and at least many instances have been covered on the site already). We can actually easily describe the number of invariant factors divisible by a fixed prime $q$ as follows.

Given $n$, the decomposition $(*)$, and a prime $q$, the number of invariant factors divisible by $q$, call it $\ell(n,q)$ is gotten as the following sum: $$\ell(n,q)=\sum_j e(p_j,q),$$ where $$ e(p,q)= \begin{cases} 2,\ &\text{if $p=q=2$ and $8\mid n$},\\ 1,\ &\text{if $p=q=2$, $4\mid n$, but $8\nmid n$},\\ 1,\ &\text{if $p=q>2$, and $p^2\mid n$},\\ 1,\ &\text{if $p\neq q$, and $q\mid p-1$},\\ 0,\ &\text{in all the other cases.} \end{cases} $$ This follows by a study of the orders of all those cyclic factors. Again, $\Bbb{Z}_n^*$ will have a quotient group isomorphic to $C_q^{\ell(n,q)}$.

Then the final answer is:

The minimum number of generators of $\Bbb{Z}_n^*$ is the maximum of the numbers $\ell(n,q)$ with $q$ ranging over the primes.

Upon reading Greg Martin's fine answer I realized that $\ell(n,2)$ is always the maximum of the numbers $\ell(n,q)$. Therefore it suffices to calculate $\ell(n,2)$, and the answer is what Greg wrote.