Clarification on the order of an element in the Pohlig-Hellman algorithm for groups whose order is a prime power

Question

According to wikipedia:

Why does $h_k=(g^{-x_k}h)^{p^{e-1-k}}$ have an order that divides p. Shouldn't the order divide $p^{k+1}$?

Answer 1

The order of $h_k$ does divide $p$; for $k=0$ this is immediate from the definition, as $$h_0:=(g^{-x_0}h)^{p^{e-1-0}}=(g^{-0}h)^{p^{e-1}}=h^{p^{e-1}},$$ and so by Lagrange's theorem the order of $h_0$ divides $p$. For every $k\geq0$ we have \begin{eqnarray*} h_{k+1}^p&=&\left((g^{-x_{k+1}}h)^{p^{e-1-(k+1)}}\right)^p\\ &=&\left(g^{-(x_k+p^kd_k)}h\right)^{p^{e-1-k}}\\ &=&\left(g^{-p^kd_k}g^{-x_k}h\right)^{p^{e-1-k}}\\ &=&g^{-p^{e-1}d_k}(g^{-x_k}h)^{p^{e-1-k}}\\ &=&\gamma^{-d_k}h_k, \end{eqnarray*} which shows that $h_{k+1}^p=e$ by definition of $d_k$, so the order of $h_{k+1}$ divides $p$.