To prove G is not cyclic Suppose that $G$ is a group of order $16$ and that, by direct computation, you know that $G$ has at least nine elements $x$ such that $x^8 =e$. How to prove that $G$ is not cyclic?
What if $G$ has at least five elements $x$ such that $x^4=e$?
Can we generalise the result?
My attempt:
If $n$ divides the order of $G$, there exist one and only one subgroup of order $n$, if $G$ is cyclic. 
Since the order of an element divides the order of the group, the number of solutions for the equation $x^n = e$ is $n$, if G is cyclic. 
Here the number of solutions is not equal to $n$ (in both the cases). Hence G is not cyclic. 
Is my proof correct? 
 A: If $G$ is cyclic then $G=\left<g\right>$ where $g$ has order $n$. Then the order of any element $g^k\in G$ is
 $$\text{order}(g^k)=\dfrac{n}{\text{gcd}(n,k)}$$
Note that if $x^n=e$ then the order of $x$ divides $n$. So let's look at this for $x^n=8$ in a cyclic group of order $16$
There's only one element of order 1: $e$ thats $k=0$
Elements of order $2$: will in a cyclic group of order $16$ will be equal to the number $k=0,\ldots,15$ such that 
$$
2=\frac{16}{\text{gcd}(16,k)}
$$
That is $\gcd(16,k)=8$ which means. $k=8$ is the only option. 
Elements of order 4: The formula gives $\gcd(16,k)=4$ hence $k=4,12$
Elements of order 8: The formula gives $\gcd(16,k)=2$ hence $k=2,6,10,14$
So in total the powers $k=0,8,4,12,2,6,10,14$ are the only elements in a cyclic group that can satisfy $x^8=e$. Since you have 9 elements with this property, they group can't be cyclic. 
A much more efficient approach is to use the complementary order. How many elements have order 16? You can use the Euler Totient function for this (someone else did that). But you can also use the above formula. Suppose 
$$16=\dfrac{16}{\text{gcd}(16,k)}$$
Then $\gcd(16,k)=1$ so the powers $k=1,3,5,7,9,11,13,15$ all give elements of order 16 which cannot satisfy $x^8=e$. Since your group has $16$ elements and $9$ that satisfy the equation that leaves at most $7$ powers that won't satistfy $x^8=e$.

What if $G$ has at least five elements $x$ such that $x^4=e$? Can we
  generalise the result?

A cyclic group of order 16 has exactly 4 elements of order dividing 16 namely the powers $k=0,8,4,12$. Therefore, any group with 5 elements satisfying $x^4=e$ also cannot be cyclic. 
Similarly any group of order 16 with more than two elements satisfying $x^2=e$ is not cyclic because a cyclic group of order $16$ only has two such powers $k=0,8$
A: If $G$ is an abelian group, then, for $d$ a nonnegative integer,
$$
G[d]=\{x\in G:x^d=e\}
$$
is a subgroup of $G$. If $G$ is finite, then you can apply Lagrange’s theorem.
With $|G[8]|>9$ and $|G|=16$, the only possibility is that $G[d]=16$; can $G$ be cyclic?
Can you compute $G/G[d]$ when $G$ is cyclic and $d$ divides $|G|$? This will provide the clue for the second part.
A: A short proof goes like this: 
If G is cyclic and $|G|=16$, then you know from group theory that G has $\phi(16)$ number of generators, i.e elements of order 16, where $\phi$ is the euler totient function. However $\phi(16)=8$ and thus there are exactly 8 elements of order 16, which means that there are 16-8=8 elements of order less than 16 (8 or lower), which is a contradiction, since by hypothesis we have 9 elements with order $\leq 8$. Always have in mind that if $x^n=e$ that does not mean that $ord(x)=n$, but only that $ord(x) | n$, which I think you have confused in your proof.
Now to your proof: The result you have written is indeed correct but for another reason. When |G|=16 cyclic, G is a cyclic p-group. As you mentioned for every $n | 16 $, $\exists !$ subgroup H of order n. Because of the fact that the group is a cyclic subgroup you can prove then if $H_1, H_2$ subgroups with orders $|H_1| < |H_2|$, then $H_1 \leq H_2$. If we denote $H_n$ the subgroup of order n, what that means is that every element x which $x^8=1$ lives in $H_8$, i.e $x\in H_8$. The same is true for, say all the elements with $x^4=1$, you can conclude that $x\in H_4$. Let me expand on this in case it is not clear.
Suppose $x^4=1$. That means either that ord(x)=1 or 2 or 4. If $ord(x)=4$ then $x\in H_4$, but there is only one $H_4$. If ord(x)=2, then $x\in H_2$, but there is only one $H_2$. Very easilly you can see $H_2 \leq H_4$ and thus $x \in H_4$. If at last $ord(x)=1$, i.e $x=e$ then obviously $e\in H_4$. As a result you can say that $H_4=\{x \in G : x^4=1\} $ and so on for every $n |16$  (I used n=4 to be easier understood). 
A: Suppose for the sake of argument we assume that G is cyclic.Now The group contains elements of orders 1,2,4,8,16.Elements of order 16 are phi(16) in number and phi(16)=8,therefore elements of order<16 are 16-8=8 in number.Exactly these elements satisfy the eqn x^8=e.Hence there cannot be more than 8 elements satisfying the eqn.So G cannot be cyclic.
Another proof:8 divides 16,hence G has exactly one subgroup of order 8.Each element in that subgroup satisfies the eqn.Now if any other element satisfies the eqn then its order<16 viz 1,2,4,8.If there is an element with one of these order,then we can form a subgroup of one of these order,but there is already a subgroup of each of these order present in the subgroup of order 8(because it its cyclic,so for each divisor,a subgroup).Thus we have 2 subgroups of same order of cyclic group G,which is a contradiction.Thus,G cannot be cyclic.
A: Any cyclic group of order $n$ contains exactly one subgroup of order $d$, with $d$ a divisor of $n$, and the subgroup being cyclic. Because of this, $C_{16}$ contains $1$ element of order $1$, $1$ element of order $2$, $2$ of order $4$ (these are the $2$ generators of $C_4$ in $C_{16}$), and $4$ of order $8$ (the $4$ generators of $C_8$), so in total only $8$ elements satisfying
$x^8=1$. :) 
