Fundamental theorem of finite Abelian group

Question

In Gallian's Contemporary Abstract Algebra, he mentioned about this Greedy Algorithm for an Abelian group. It's basically a procedure of expressing a finite Abelian group as an internal direct product which is a result from fundamental theorem of finite Abelian group. But the validity of the algorithm is not clear for me.

The algorithm is given as follows:

Greedy Algorithm for an Abelian Group of Order $p^n$ ($p$ is prime)

1. Compute the orders of the elements of the group $G$.
2. Select an element $a_1$ of maximum order and define $G_1=\langle a_1\rangle$.
3. If $|G_1|=|G|$, stop. Otherwise, replace $i$ by $i+1$.
4. Select an element $a_i$ of maximum order $p^k$ such that $p^k\leq|G|/|G_{i-1}|$ and none of $a_i$, $a_i^p$, $a_i^{p^2}$,..., $a_i^{p^{k-1}}$ is in $G_{i-1}$ and define $G_i=G_{i-1}\times\langle a_i\rangle$.
5. Return to Step 3.

Internal direct product requires that none of the elements of $\langle a_i\rangle$ except identity should be in $G_{i-1}$ so why the condition in step 4 is weaker?

Answer 1

As written, the algorithm is... poorly defined. I guess that you meant:

Let $i=1$, and $G_0= \emptyset$.

1. Compute the orders of the elements of the group G.
2. Select an element $a_i$ of maximum order $p^k$ such that $p^k\leq|G|/|G_{i-1}|$ (not sure this is necessary to state) and such that none of $a_i, a_i^{p}, \dots , a_i^{p^{k-1}}$ is in $G_{i-1}$ and define $G_i=G_{i-1} \times ⟨a_i⟩$.
3. If $|G_i|=|G|$, stop. Otherwise, replace $i$ by $i+1$. and repeat step 2.

That being said, you are asking why it is enough to restrict attention to powers of $a_i$ that have a power of $p$ as exponent. The answer is that $a_i^p$ and $a_i^{pq}$ whenever $q$ does not divide $p$ generate the same subgroup. In fact, $G$ is a $p$-group and all elements have order $p^m$ for some $m \in \mathbb{N}$, so $a_i^{pq}$ has to have the same order as $a_i^p$. So this seemingly weaker hypothesis is actually equivalent to the standard requirement.