Take the 2-minute tour ×

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.

share|improve this question
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
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
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... –  sasha Oct 6 '11 at 7:49
add comment

Your Answer


