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.


1 Answer 1


Looks sound and direct to me. There is only minor copy-editing to do, such as:

  • 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$."

  • To make the structure of the proof more explicit, you could write "Conversely," rather than "Now," at the beginning of the third paragraph. This tells the reader that you have now finished something and is proceeding to the opposite direction of what you just proved.

  • Calling the other prime $q$ would be somewhat more conventional than $\alpha$.

  • $\begingroup$ Great, thank you for the suggestions. Last thing--if you could judge from this one post, would you say that my mathematical writing is verbose overall? Definitely would like to change that... $\endgroup$
    – AndJM
    Oct 6, 2011 at 7:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .