Suppose that $a_1,\ldots,a_k$ are elements of the finite cyclic group $\mathbb{Z}/n\mathbb{Z}$. They generate a cyclic subgroup $\langle m\rangle$. Then for each $i$ we may write $a_i=mb_i$ for some $b_i\in \mathbb{Z}/n\mathbb{Z}$. Generally there are many possible choices for the elements $b_i$ (e.g. if $n=6$ then $4=2\cdot 2=2\cdot 5$, everything modulo $6$). Can we always choose $b_1,\ldots,b_k$ such that they generate $\mathbb{Z}/n\mathbb{Z}$?
This seems like a very simple question and my guess would be that it's true but I'm having a surprisingly hard time proving it...
Hint. First suppose that $n =p^s$ for some prime $p$. Let $a_i = p^{r_i}c_i$ with $c_i$ prime to $p$ and let $r = \min r_i$. Without loss of generality, we may assume that $r = r_1$. Then the $a_i$'s generate (modulo $n$) the cyclic group with generator $m = a_1$, so we can choose $b_1 = 1$, which generates $\Bbb Z/n\Bbb Z$.
Now use the fact that $\Bbb Z/n\Bbb Z$ is a product of groups of the form $\Bbb Z/p^s\Bbb Z$ to treat the general case.