The so-called pseudosquares can be employed in very powerful machinery for the primality testing of integers N. In fact, assuming reasonable heuristics (which have been confirmed for numbers to 280) they can be used to provide a deterministic primality test in time O(log N)³ + o(1), which some believe to be best possible. In the 1980s D.H. Lehmer posed a question tantamount to whether this could be extended to pseudo r-th powers. Very recently this was accomplished for r = 3, which naturally leads to the question of whether anything can be achieved for r > 3. In this paper we show how these earlier results can be extended to all prime values of r.