In a paper there is a lemma:

Let $G= \langle a,b \rangle$ be a finite cyclic group. Then $G=\langle ab^n \rangle$ for some integer $n$.

The proof is omitted because it's "straightforward" but I'm not able to proof it. How does this work?

  • 5
    $\begingroup$ If $G$ is cyclic then by definition it is generated by one element, say $G = \langle x \rangle$. Then $a=x^\alpha$ and $b=x^{\beta}$ for some $\alpha, \beta$. Then $ab^n=x^{\alpha+n\beta}$; you need to show that, given that $a,b$ cenerate $G$, an $n$ exists such that $x^{\alpha+n\beta}=x$. $\endgroup$ – Clive Newstead Aug 6 '12 at 22:31
  • 2
    $\begingroup$ This doesn't always work, consider for example the case $\alpha=2$, $\beta=3$, $|G|=6$. Then $2 + 3n \not{\equiv} 1 \pmod{6}$. $\endgroup$ – Yuval Filmus Aug 6 '12 at 23:14
  • $\begingroup$ @YuvalFilmus On the other hand, $2+3=-1$, which is also a generator of $\mathbb{Z}/(6)$. $\endgroup$ – KReiser Aug 6 '12 at 23:38
  • $\begingroup$ @KReiser: absolutely, the theorem still holds in this case; but @Yuval’s point I think was that @Clive’s outlined solution doesn’t always work, with (2,3,6) giving a counterexample. $\endgroup$ – Peter LeFanu Lumsdaine Aug 7 '12 at 13:45

Yuval's solution, sans Dirichlet: let $n$ be the product of all the primes that divide the order of $G$ but don't divide $x$. Then $\gcd(x+ny,|G|)=1$.

Proof: Let $p$ be a prime dividing the order of $G$. If $p$ divides $x$, then it doesn't divide $y$ (since $\gcd(x,y,|G|)=1$), and it doesn't divide $n$ (by construction), so it doesn't divide $ny$, so it doesn't divide $x+ny$.

If $p$ doesn't divide $x$, then it divides $n$ (by construction), so it divides $ny$, so it doesn't divide $x+ny$. So no prime dividing the order of $G$ divides $x+ny$.


Without loss of generality, $a,b \neq 1$. For $g$ a generator of $G$, we have $a = g^x$ and $b = g^y$, where $(x,y) = 1$. By Dirichlet's theorem, there is $n > |G|$ such that $x + ny$ is prime, so that $(x+ny,|G|) = 1$. Therefore $ab^n = g^{x+ny}$ generates $G$.

Edit: As commented below, we actually only know that $d=(x,y)$ is relatively prime to $|G|$. By Dirichlet's theorem, there is $n > |G|$ such that $(x+ny)/d$ is prime, and so $(x+ny,|G|)=1$.

  • 6
    $\begingroup$ Dirichlet's theorem?! Talk about nuclear.. :) $\endgroup$ – anon Aug 6 '12 at 23:07
  • 2
    $\begingroup$ $(x,y)$ isnt necessarily 1, just coprime to $|G|$ $\endgroup$ – butt Aug 6 '12 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.