R.e. prime powers and total rigidity V. Yu. Shavrukov Abstract: We introduce r.e. prime powers as the least common multiple of the recursive ultrapowers of N of Hirschfeld and the r.e. ultrapowers of N of Hirschfeld & Wheeler. R.e. prime powers help us with establishing that r.e. ultrapowers admit no non-identity self-embeddings, settling an issue raised by Hirschfeld & Wheeler. This parallels an earlier theorem by McLaughlin for recursive ultrapowers. The road to solution takes us through a number of variants of recursive/online forest colouring tasks. Along the way we also take a look at a Rudin–Keisler-like category of prime filters in the lattice of r.e. sets and discover some r.e. prime powers that do admit non-trivial self-embeddings.