# For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$

I'm having a bit of difficulty writing a graceful proof for the following problem:

For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$.

Let $A$ be the set of positive integers whose greatest proper divisor is $p$. I will show that $A=\{\alpha p\,|\,\alpha \;\text{prime},\; \alpha \leq p\}$ so that $|A|=\pi(p)$, the number of primes less than or equal to $p$.

Assume that $n=\alpha p$ for some prime $\alpha \leq p$. The factors of $n$ are $1, \alpha, p, \alpha p$. (In the case that $\alpha =p$, the factors of $n$ are $1,p, p^2$.) The greatest proper divisor of $n$ therefore is $p$ and so $n\in A$.

Conversely, for any number in $A$, clearly we have that $p$ is the greatest prime dividing it. Moreover, any three primes dividing it would contradict $p$ being the greatest divisor (this can be seen in the following way: if $\alpha_1\neq \alpha_2$ are two primes dividing the number, neither of which is $p$, then we have $\alpha_1<p<\alpha_1p<\alpha_1\alpha_2p$ from which we infer that $p$ is not the greatest proper divisor.) Therefore, a number in $A$ must have at most two prime factors, one being $p$. (We can rule out that a number in $A$ has exactly the one prime factor, $p$, since it has no proper divisors.) Hence, $A\subset \{\alpha p\,|\,\alpha \;\text{prime},\; \alpha \leq p\}$.

Perhaps there's a more elegant proof, but I'm concerned with my writing style. Can anyone help me rephrase my argument in a smoother way or critique it?

edit: incorporated the changes suggested by Henning.

-
Isn't that what I did in the first paragraph? – sasha Oct 5 '11 at 22:48
perhaps you did – Henry Oct 5 '11 at 22:54

• The condition $2\le\alpha$ is redundant; it is already implied by $\alpha$ being prime.
• The part "Let $n\in\{\alpha p\,|\,\alpha \;\text{prime},\; 2\leq \alpha \leq p\}$. Then $n=\alpha p$ for some prime $\alpha$, $2\leq \alpha \leq p$" is probably more verbose than you need to be. I would just write, "Assume that $n=\alpha p$ for some prime $\alpha \leq p$."
• Calling the other prime $q$ would be somewhat more conventional than $\alpha$.