Finding cyclic subgroups of a non-cyclic group An example would be $U(16) = \{1,3,5,7,9,11,13,15\}$. I know $U(16)$ is not cyclic because the order of $7$ and $15$ is $2$. But how do you go about finding the cyclic subgroups in cases like this?
 A: This case is specialy simply: $U(16)$ is a small group $$ 16 = 2^4 \quad \therefore \quad |U(16)| = \varphi(16) = (2-1) 2^{4-1} = 8$$
and you can calculate $\langle g \rangle$ for all $g \in U(16)$. So
$$\langle 3 \rangle = \{1, 3, 9, 27 \equiv 11\}\\
\langle 5 \rangle = \{1, 5, 25 \equiv 9, 45 \equiv 13\}\\
\langle 7 \rangle = \{1, 7\} $$
and so on.
Generally, do this is not possible (because your group has infinity order or it's too big or it's boring and we have no pacient). There are some results that can be usefull:
Thm.: Let $G$ be a finite group of order $n$. $G$ is a cyclic iff for any divisor $d$ of $n$ there is at most one cyclic subgroup $H$ of $G$ with order $d$.
The proof is simple, you only use the classical result $n=\sum_{d|n}\varphi(d)$.
We have another interesting result if you are looking to $\mathbb{Z}_p$
Thm.: Let $\mathbb{K}$ a field and $\mathbb{K}^{\times}$ it's multiplicative group. Let $G$ a subgroup of $\mathbb{K}^{\times}$. If $G$ has finite order, then it's cyclic.  In particular, $\mathbb{F}_{p^n}^{\times}$ is cyclic. 
Proof: Let $n = |G|$ and $d$ a divisor of $n$. We will use the equivalence of the previous result. Suppose there are $H$ and $H'$ distinct subgroups of order $d$. By Lagrange Theorem, $h^d = 1$ for all $h \in H \cap H'$. So, the elements of $H \cap H'$ are roots of $f(x) = x^d - 1 \in \mathbb{K}[x]$, but $$|H \cap H'| \leq \{k \in \mathbb{K} \mid f(k) = 0\} \leq \deg f(x) = d < |H \cap H'|$$ Contradiction. Therefore, there is at most one subgroup of order $d$ and $G$ is cyclic.
I think I should mention the Cauchy's Theorem:
Thm (Cauchy).: Let $G$ be a finite group and $p$ a prime. If $p$ divides $|G|$, there is $g\in G$ with order $p$, i.e. , there is a cyclic subgroup $H = \langle p \rangle$ with order p.
(See here for details and proofs). Note, Cauchy's result don't tell you how to find some cyclic subgroup, but it say that there is at least one cyclic group with order $p$.

Edit: Probably, I should do a example. Let's try $U(140)$. We know that $$ 140 = 2^2 \cdot 5 \cdot 7 \\ \therefore |U(140)| = \varphi(140) = (2-1)2^{2-1} (5-1) 5^{1-1} (7-1)7^{1-1} = 48  = 2^4 \cdot 3$$
Then there is at last one cyclic subgroup of $U(140)$ with order 2 and 3. If you show that there are more then one subgroup woth order 2 or 3, then the first theorem says that $U(140)$ is not cyclic. Of course $-1$ have order 2 $$\langle -1 \rangle = \{1, -1\}$$ and we only need to find another element with  order $
2$ (I guess this is what you did in your example). Let's try some numbers not divisible by 2, 5 and 7, maybe prime numbers are a good idea. I tried some random numbers with Wolfram's  help and $$\langle 29 \rangle = \{1, 29\} \\ \langle 41 \rangle  = \{1, 41\}\\ \langle 99 \rangle = \{1, 99\} \\ \langle 111 \rangle = \{1, 111\}$$
Yeah, it's enought. So $U(140)$ is not cyclic. On particular there is no field $\mathbb{K}$ such that $U(140)$ is a subgroup of $\mathbb{K}^{\times}$.
But how many cyclic subgroup we can find? Here is a partial answer: We could use Sylow Theorems.
Thm (3º Sylow) Let $G$ a finite group with order $n$ and p be a prime factor such that $n = p^m b$ with $gcd(p,b)=1$ Let $n_p$ be the number of Sylow p-subgroups of G (subgroup with order $p^m$). Then the following hold:
1) $n_p$ divides the index of the Sylow p-subgroup in G;
2) $n_p \equiv 1 (mod p)$;
3) $n_p = |G : N(P)|$, where $P$ is any Sylow p-subgroup of $n$ and $N$ denotes the normalizer.
Using it in our example, we know that $$n_3 \mid |U(140)/3| = 2^4 \Rightarrow n_3 \in \{1, 2, 4, 8, 16\}$$ and $$n_3 \equiv 1 mod(3) \Rightarrow n_3 \in \{1, 4, 16\}$$
Ok, we know  (without boring computations) that $U(140)$ is not cyclic; ok, we   don't know how many subgroups with order 3, but we know that there are 1, 4 or 16. In this example, with a computer we can test some numbers and do a full list of cyclic subgroups because it's finite. For example, I discovered that is just one subgroup with order 3 $$\langle 81 \rangle = \langle 121 \rangle = \{1, 81, 121\}$$
A: $U_{16}$ is not cyclic because none of its elements have order $\varphi (16)=2^4-2^3=8$.
Each element of a group generates a cyclic subgroup of size (cardinality) equal to the order of the element.
Some elements may generate the same cyclic subgroup.
To wit, I proved a very useful result related to finding generators of a cyclic group (once you have a first one) over here.
