  Extending earlier work of Guralnick and of Cai and Zhang, we classify the
almost simple groups which have transitive permutation representations of prime
power degree $p^k$, and those which have $p$-complements (stabilisers of order
coprime to $p$ in such representations). We deduce that every primitive
permutation group of prime power degree has a regular subgroup, and that any
two faithful primitive representations of a group, of the same prime power
degree, are equivalent under automorphisms. In general, $p$-complements in a
finite group can be inequivalent under automorphisms, or even non-isomorphic.
We extend examples of such phenomena due to Buturlakin, Revin and Nesterov by
showing that the number of inequivalent classes of complements can be
arbitrarily large. Questions concerning the existence of prime power
representations and $p$-complements in groups with socle ${\rm PSL}_d(q)$ are
related to some difficult open problems in Number Theory.
