How do I prove this greatest common divisor problem?

Question

Let $n\in\mathbb{Z}^{+}\!,\;k \in (\mathbb{Z}_n,+),\;\text{and}\;d=\gcd(k,n)$.

Prove that $\langle k \rangle = \langle d \rangle$.

Not sure how to prove this one, any thoughts?

Answer 1

Let $\langle k \rangle$ and $\langle d \rangle$ denote the subgroups of $\mathbb{Z}_n$ generated by $k,d$ respectively. \begin{align*} \text{Then}\;\;&d= \gcd(k,n)\\[4pt] \implies\;&d|k\\[4pt] \implies\;&k=dx,\;\text{for some integer $x$}\\[4pt] \implies\;&k\in \langle d \rangle\\[4pt] \implies\;&\langle k \rangle \subseteq \langle d \rangle\\[10pt] \text{Also,}\;\;&d=\gcd(k,n)\\[4pt] \implies\;&ak + bn = d,\;\text{for some integers $a,b$}\;\,\text{[by Bezout's Theorem]}\\[4pt] \implies\;&ak \equiv d\;(\text{mod}\; n)\\[4pt] \implies\;&d\in \langle k \rangle\\[4pt] \implies\;&\langle d \rangle \subseteq \langle k \rangle\\[4pt] \end{align*} Therefore $\langle k \rangle = \langle d \rangle,\;$as was to be shown.