Every subgroup of $\mathbb{Z}/n\mathbb{Z}$ is cyclic. My teacher gave us this exercise to think, she'll do it tomorrow on class (I hope). I've been thinking but I don't know how to start, if somebody could give me a hint, I would appreciate so much:

Prove that every subgroup of $\mathbb{Z}/n\mathbb{Z}$ is cyclic.

Thank you.
 A: Subgroups of $\mathbf{Z}/n\mathbf{Z}$ correspond, by inverse image by the canonical projection $\mathbf{Z}\to \mathbf{Z}/n\mathbf{Z}$, to subgroups of $\mathbf{Z}$ containing $n\mathbf{Z}$, that is, as $\mathbf{Z}$'s subgroups are cyclic, to subgroups $d\mathbf{Z}$ such that $d|n$, so that subgroups of $\mathbf{Z}/n\mathbf{Z}$ are of the form $d\mathbf{Z}/n\mathbf{Z}$, with $d|n$. Finally, note that $d\mathbf{Z}/n\mathbf{Z}$ is but the sub-group of $\mathbf{Z}/n\mathbf{Z}$ generated by the image of $d$ in $\mathbf{Z}/n\mathbf{Z}$, a cyclic group.
A: Hint: Let $H \leq \mathbb Z/n\mathbb Z$ be a subgroup, take the smallest positive $a \in \mathbb Z$ such that $a \in H$.
(Note by $a \in H$ I really mean $a + n\mathbb Z \in H$, but it's common to just write $a \in H$)
A: Every subgroup $H ⊂ ℤ/nℤ$ is finite. If $x_1, …, x_d ∈ ℤ$ represent all elements of $H$, then consider $x = \gcd (x_1, …, x_d)$. Now answer these questions (with a proof):


*

*Does $x$ represent an element of $H$?

*How can you express the elements of $H$ in terms of $[x]_{nℤ}$?

A: It is no harder to show a more general result: Any subgroup of a cyclic group is cyclic. Then as $\mathbb{Z}/n\mathbb{Z}$ is cyclic, you have your answer and a more general result to boot!
To show this, suppose the original cyclic group is generated by $g$. Then for some power $n$, $g^n$ must be in your subgroup. Take the smallest such $n$. Then show that $g^n$ must generate your subgroup. To do this, you will want to make use of the division algorithm:

If m and n are integers and n is positive, then there are unique integers q and r such that m=nq+r and 0≤r

