Let $G$ be a finite abelian group of order $n$.
Procedure to compute the order of elements
- For $x \in G$
- Compute $x^2,x^3,\cdots,x^{k =\text{ord}(x)}$
- Now with the help of $x^{k}$ compute the order of $x^2,x^3\cdots x^{k-1}$ by using formula $\text{ord}(x^{k}) = \text{ord}(x)/\text{gcd}(\text{ord}(x),k)$.
Claim : If in the two step we went upto $k$ such that $x^k = e$ then we will compute the order of at least $k/2 - 1$ other elements ( new elements whose order is not known )
Suppose that we are storing the order of all the elements in a table. while computing the order of an element we will check whether it's order is already computed or not. In simple words in the third step we will compute the order of only those elements whose order is not known
I have tried like assume that $x$ generate the whole group $G$ in that case the above claim is true. To me it appears that each time we are computing a subgroup generated by element $x$. I don't above claim is true or no?