1. ## Generating a group

1,000,000 < 2^20

Know that until you have a generating set, you can show that you keep adding elements so the prodcuts of each subset are different.

Prove by induction that you can generate any group of at most 2^k elements w/ k generators. Assume that you ahve a group G w/ a subgroup H, generated by k elements.

If g is an element of G not in H, the subgroup generated by the generators of H and g contains all the products gh for all h in H.

Try to prove all elements are distinct, and none exist in H. THis means that starting w/ a subgroup H generated by k elements you can add a generator and get a subgroup twice (at least) as large as H.

Your help will be GREATLY appreciated, thank you.

1,000,000 < 2^20

Know that until you have a generating set, you can show that you keep adding elements so the prodcuts of each subset are different.

Prove by induction that you can generate any group of at most 2^k elements w/ k generators. Assume that you ahve a group G w/ a subgroup H, generated by k elements.

If g is an element of G not in H, the subgroup generated by the generators of H and g contains all the products gh for all h in H.

Try to prove all elements are distinct, and none exist in H. THis means that starting w/ a subgroup H generated by k elements you can add a generator and get a subgroup twice (at least) as large as H.

Your help will be GREATLY appreciated, thank you.
let $G$ be a group with $|G| \leq 2^k, \ k \in \mathbb{N}.$ 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.$ note that $G_1 \cap g_2G_1 = \emptyset,$ because

$g_2 \notin G_1,$ and $G_2 \supseteq G_1 \cup g_2G_1.$ thus $|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 again $G_2 \cap g_3G_2 = \emptyset$ and

$|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 $g \in G \setminus G_r.$ that

means $\langle g_1,g_2, \cdots , g_r \rangle = G_r=G.$ but then $2^k \geq |G|=|G_r| \geq 2^r$ and so $r \leq k.$ thus $G$ can be genrated by $r \leq k$ elements.