Number of generators of a finite group

Posted: May 11, 2010 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: , ,

Problem. Prove that a group $G$ with $|G| \leq 2^n, \ n \in \mathbb{N},$ can be generated by $n$ elements.

Solution.  Let $1 \neq g_1 \in G$ and put $G_1=\langle g_1 \rangle.$ Then $|G_1| \geq 2.$ Now, if possible, choose $g_2 \in G \setminus G_1$ and put $G_2=\langle g_1,g_2 \rangle.$ Then $G_2 \supseteq G_1 \cup g_2G_1$ and therefore

$|G_2| \geq |G_1 \cup g_2G_1|=|G_1| + |g_2G_1|=2|G_1| \geq 2^2.$

Again, if possible, choose $g_3 \in G \setminus G_2$ and put $G_3=\langle g_1,g_2,g_3 \rangle.$ Then

$|G_3| \supseteq |G_2 \cup g_3G_2|=2|G_2| \geq 2^3.$

Continuing this way we will eventually find some $r \in \mathbb{N}$ and $G_r=\langle g_1, g_2, \cdots , g_r \rangle$ with $|G_r| \geq 2^r$ and it is no longer possible to choose any $g \in G \setminus G_r.$ That means $\langle g_1,g_2, \cdots , g_r \rangle = G_r=G.$ But then we’ll have $2^n \geq |G|=|G_r| \geq 2^r$ and so $r \leq n.$ Thus $G$ can be genrated by $r \leq n$ elements. $\Box$