D. H. Lehmer initiated the study of the distribution of totatives, which are numbers coprime with a given integer. This led to various problems considered by P. Erdős, who made a conjecture on such distributions. We prove his conjecture by establishing a theorem on the ordering of residues.