Number of elements of order k in the multiplicative group $(\Bbb{Z}/n\Bbb{Z})^*$ I know that if $n$ is a prime and if $k$ divides $n-1$ then there will be $\phi(k)$ elements of order $k$ in this group, but does this extend for when $n$ is not a prime? can I say that if $k$ divides $\phi(n)$ then there are $\phi(k)$ elements of order $k$?
 A: We know that $(\mathbb{Z}/n\mathbb{Z})^*$ is cyclic if and only if $n$ is a power of an odd prime, twice the power of an odd prime, of equal to $2$ or $4$ (the only values of $n$ that have primitive roots). In  those cases, it is easy.
But for more general $n$ it becomes complicated. Using the Chinese Remainder Theorem, we can decompose $\mathbb{Z}/n\mathbb{Z}$ into a direct product of cyclic groups of prime power order, which in turn will decompose $(\mathbb{Z}/n\mathbb{Z})^*$ into unit groups of cyclic groups of prime power order. Namely, if
$$ n= 2^{a} p_1^{a_1}\cdots p_r^{a_r},$$
where $2\lt p_1\lt\cdots \lt p_r$ are primes, $a\geq 0$, $a_i\gt 0$ for all $i$, then
$$\mathbb{Z}/n\mathbb{Z} \cong \frac{\mathbb{Z}}{2^a\mathbb{Z}} \times \frac{\mathbb{Z}}{p_1^{a_1}\mathbb{Z}}\times\cdots\times \frac{\mathbb{Z}}{p_r^{a_r}\mathbb{Z}},$$
and since an element in the direct product is a unit if and only if each component is a unit, we obtain that
$$\left(\frac{\mathbb{Z}}{n\mathbb{Z}}\right)^* \cong \left(\frac{\mathbb{Z}}{2^a\mathbb{Z}}\right)^*\times \left(\frac{\mathbb{Z}}{p_1^{a_1}\mathbb{Z}}\right)^*\times\cdots\times \left(\frac{\mathbb{Z}}{p_r^{a_r}\mathbb{Z}}\right)^*.$$
We know the decomposition type in each of those cases: it will be cyclic group of order $(p_i-1)p_i^{a_i-1}$ each of the odd primes, it will be cyclic of order $2^{\max(0,a-1)}$ for the $2^a$ factor if and only if $a\leq 2$; and if $a\gt 2$, then it will be isomorphic to $(\mathbb{Z}/2\mathbb{Z})\times(\mathbb{Z}/2^{a-2}\mathbb{Z})$. 
Now, an element will have order $k$ if and only if the lcm of the orders of the components is equal to $k$. So you first have to count all possible combinations of elements positive integers $(d_{-1},d_0,d_1,\ldots,d_r)$ such that $d_{-1}=1$ if $a\leq 1$, and $d_{-1}|2$ otherwise; $d_0|2^{\max(0,a-2)}$, and $d_i|(p_i-1)p_i^{a_i-1}$ for $i=1,\ldots,r$, such that $\mathrm{lcm}(d_{-1},d_0,d_1,\ldots,d_r)=k$, and then you will have $\prod_{i=-1}^r\phi(d_{i})$ elements corresponding to that "signature."
This is going to be difficult in general, and I doubt if there is a nice (or even a complicated) formula for it.
In the special case where $k$ is prime we have better luck: in order for the lcm to be $p$ each component must be of order $p$ or of order $1$. 
If $k=2$, then the number of elements of exponent $2$ is $2^r$ if $a\leq 1$; $2^{r+1}$ if $a=2$, and $2^{r+2}$ if $a\gt 2$.
If $k=p_i$, then let $t$ be the number of $j$ such that $p_i|p_j-1$. Then the number of elements of exponent $p_i$ is $p_i^t$ if $a_i=1$, and $p_i^{t+1}$ if $a_i\gt 1$; i.e., $p_i^{t+\min(1,a_i-1)}$.
If $k$ is an odd prime different from all $p_i$, hen let $t$ be the number of $k$ such that $k|p_j-1$. Then the number of elements of exponent $k$ is $k^t$. 

Added.
For $k=p^b$ a prime power, $b\gt 1$, you can proceed more or less similarly: count how many elements of order dividing $k$ there are, and then subtract the number of elements of order dividing $p^{b-1}$.
In the factor corresponding to $(\mathbb{Z}/p_i^{a_i}\mathbb{Z})^*$, you will have $\gcd(p^b,\varphi(p_i^{a_i})$ elements of order dividing $p^b$; in the factor corresponding to $(\mathbb{Z}/2^a\mathbb{Z})^*$, you will have $2\gcd(p^b,2^{a-2})$ if $p=2$, and $1$ if $p$ is odd. 
For an arbitrary $k$, you would want to count the number of elements of exponent $n$, and then do inclusion-exclusion over the number of elements of exponent a proper divisor of $n$ (in the prime-power case you have a better case because every element of order a proper divisor must be of exponent $p^{b-1}$, but for example for $n=6$, you would need to count the number of elements of exponent $6$, subtract those of exponent $2$ and of exponent $3$, and then add back those of exponent $1$). You can count them using gcds as above. But I think it would look like a really ugly expression with lots of cases.
