I would like to prove the correctness of the Pohlig-Hellman algorithm, but I am having difficulties dealing with the case for groups of prime-power order, specifically the first part of this wikipedia article:
https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm
I understand the concept and why it works, but I don't know how I should go about proving it formally.
I am thinking of induction, but it is not clear on what I should induct.