which numbers occur as the order of elements of $(\mathbb Z /35 \mathbb Z)^*$? which numbers occur as the order of elements of $(\mathbb Z /35 \mathbb Z)^*$? This is what I did:
First I calculated that $\#(\mathbb Z / 35 \mathbb Z)^* = \phi (35) = 24 = 2^33$. Now for any $\bar{x}\in (\mathbb Z / 35 \mathbb Z)^*$ we know that $\operatorname{ord}(x)|24$ so that all possibilities for the orders of elements are $1,2,3,4,6,8,12$ and $24$. Obviously $\bar{1}$ has order $1$. Now I saw that $\bar{2}$ and $\bar{3}$ both have order $12$ and that $\bar{6}$ has order $2$ just by checking. By the fact that $\bar{2}$ has order $12$ I deduce that $\bar{4} = \bar{2}^2$ has order $6$ and that $\bar{16}=\bar{4}^2$ has order $3$. Thus so far I have found elements of order $1,2,3,6$ and $12$. If there are any elements $\bar{x}$ of order $4$ they would satisfy $\bar{x}^2 = \bar{6}$. Similarly for any element of order $8$. So I foresee that there are no elements of order $4$ and $8$. 
I don't think my working here is rigorous enough. Are there any useful theorems I could use here to show the answer in a faster or easier way? Also, is it correct that there are no elements of order $4$ or $8$ and if so how can I prove it? Thanks in advance
 A: Hints:


*

*If $\gcd(a,35)=1$ show using Little Fermat that $a^{12}\equiv1\pmod5$ and $a^{12}\equiv1\pmod7$. Conclude that the orders of elements are factors of $12$.

*Find an integer such that $a\equiv2\pmod 5$ and $a\equiv1\pmod7$. Show that $a$ is of order $4$.

A: Your solution is perfectly rigorous (unless you want to use formal languages -I don't think so-). What you may want is more generalizable arguments. An (efficient) algorithm would be nice, I guess.
This theorem may be useful:

Let be $m\geq 2$ an integer. Then there exists a primitive root $a$ of $m$ (that is, $\text{ord}(a)=\varphi(m)$) if and only if $m$ is $2$, $4$, $p^\alpha$ or $2p^\alpha$, where $p$ is an odd prime and $\alpha\geq 1$.

Note that if $m$ has a primitive root, then the group $\Bbb Z_m^*$ has elements of every possible order: indeed, if $\text{ord}(a)=\varphi(m)$ and $d$ is any divisor of $\varphi(m)$, then $a^{\varphi(m)/d}$ has order $d$.
Nevertheless, in Introduction to Analytic Number Theory of Tom M. Apostol, Springer, p. 212, it says:

Although we have shown the existence of primitive roots for certain moduli, no direct method is known for calculating these roots in general without a great deal of computation, specially for large moduli.

In the same book there is no mention of general, efficient methods for solving the equation $x^n\equiv 1\pmod m$ given $m$ and $n$, or even for deciding whether it has any solution, so I assume that there aren't any.
Sylow's theorems can also be in handy. In any finite group (even a non-commutative group) of order $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ it is guaranteed that there are subgroups of order $p_j^{\alpha_j}$ for every $1\leq j\leq k$. (In fact, in a commutative group, there is exactly one subgroup of order $p_ j^{\alpha_j}$ for each $j$). Then there must be elements of order $p_j$ for each $j$.
