Simple Cyclic Group Proof 
Theorem: Subgroups of a cyclic group is cyclic.


So I pretty much understood the whole proof, but the first comment. Why do we "let $m$ be the smallest integer such that" to start the proof? I know this is where the contradiction lies, but my question is specifically asking what gave us the idea to pick the smallest, and not the biggest, or some other "middle" number?
EDIT: Doesn't this condition actually force $m = 1$ always? 
 A: Here is another proof that may shed some light on why we do that.
Let $S$ be the set of all $n$ in $\mathbf{Z}$ such that $a^n \in H$. Then I claim that $S$ is a subgroup of $\mathbf{Z}$.
This is because if $a^p$ and $a^q$ are both in $H$, then so are $a^{p+q}$ and $a^{-p}$. Also, $a^0$ is in $H$. (A more sophisticated way to phrase the same proof is to say that $n \mapsto a^n$ is a morphism from $\mathbf{Z}$ to $G$, and that $S$ is the inverse image of $H$ under this morphism, and is therefore a subgroup of $\mathbf{Z}$.)
Now the important basic fact to complete the proof is that any subgroup of $\mathbf{Z}$ is of the form $d\mathbf{Z}$ for some integer $d \geq 0$, i.e., it is the subgroup generated by $d$.  Thus the powers of $a$ that are in $H$ are all $a^{dk}$, and $H$ is generated by $a^d$.
The "basic fact" I've just referred to is proved by an argument similar to the one above, using division. You start by saying "If $S \ne \{0\}$, then let $d$ be the smallest positive integer in $S$," etc.
To see why we take the smallest positive integer $d$, let's assume temporarily that we already know the basic fact, that we have some subgroup $S$ of $\mathbf{Z}$, and that we are interested in finding a generator of $S$.
The basic fact says that all subgroups of $\mathbf{Z}$ are in the following list:
$\{0\}$
$\{0, \pm1, \pm 2, \pm 3, \ldots \}$
$\{0, \pm2, \pm 4, \pm 6, \ldots \}$
$\{0, \pm3, \pm 6, \pm 9, \ldots \}$
$\ldots$
Now by the basic fact, you know $S$ is one of the groups in the list, but you don't know which one. How would you describe a generator of $S$? Well, in the last example of the list, a possible generator is $3$. (The only other choice is $-3$.) If you don't know which group in the list you're dealing with, you can't say for sure whether the generator will be 2, 3, 11, or another number. But the smallest positive element of the group will always generate the group. 
So if you didn't know the basic fact, but wanted to prove it, you would start by taking the number that you expect will eventually be proved to be a generator of the group, that is, its smallest positive element.
A: I offer you a different proof that uses homomorphisms and the well known fact that the subgroups of $\mathbb{Z}$ are the subsets of the form $m\mathbb{Z}$, for $m\ge0$.
If $G$ is cyclic, then there exists a surjective group homomorphism
$$
\varphi\colon \mathbb{Z}\to G
$$
(where $\mathbb{Z}$ is a group with respect to addition, of course). Let $k\mathbb{Z}$ be the kernel of $\varphi$ ($k\ge0$). The homomorphism is defined as soon as we fix a generator $g\in G$: $\varphi(n)=g^n$, for $n\in\mathbb{Z}$.
If $A$ and $B$ are subsets of $\mathbb{Z}$ and $G$ respectively, I'll set
\begin{align}
\varphi^{\to}(A)&=\{\varphi(x):x\in A\}\\
\varphi^{\gets}(B)&=\{x\in\mathbb{Z}:\varphi(x)\in B\}
\end{align}
(the usual direct and inverse images).
If $H$ is a subgroup of $G$, then $\varphi^{\gets}(H)$ is a subgroup of $\mathbb{Z}$ containing $k\mathbb{Z}$. Therefore $\varphi^{\gets}(H)=m\mathbb{Z}$ for a unique $m\ge0$, and $m\mid k$.
Since $\varphi$ is surjective, we have $H=\varphi^{\to}(\varphi^{\gets}(H))$ and therefore $\varphi$ induces a (surjective) group homomorphism
$$
\varphi'\colon\varphi^{\gets}(H)=m\mathbb{Z}\to H.
$$
Since $m\mathbb{Z}$ is cyclic and generated by $m$, also $H$ is cyclic and generated by $\varphi'(m)=\varphi(m)=g^m$.

Note that, when $m>0$ (that is, $H\ne\{e\}$, $m$ is the least positive element in $\varphi^{\gets}(H)$, which exactly corresponds to your choice of $m$ as the minimum positive integer such that $g^m\in H$.
The condition $m\mid k$ is not relevant for the proof, but can be used to prove supplemental facts about this situation.
As a final comment, I find that discussing cyclic groups without homomorphisms is a waste of time, because the same facts are proved again and again.
