10
$\begingroup$

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
    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$.2012-08-06
  • 2
    This doesn't always work, consider for example the case $\alpha=2$, $\beta=3$, $|G|=6$. Then $2 + 3n \not{\equiv} 1 \pmod{6}$.2012-08-06
  • 0
    @YuvalFilmus On the other hand, $2+3=-1$, which is also a generator of $\mathbb{Z}/(6)$.2012-08-06
  • 0
    @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.2012-08-07

2 Answers 2

6

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$.

1

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
    Dirichlet's theorem?! Talk about nuclear.. :)2012-08-06
  • 2
    $(x,y)$ isnt necessarily 1, just coprime to $|G|$2012-08-06