# Question on primes.

Let $p(n)$ denote the number of primes less than $n$. Show that there are infinitely many $n$ for which $n$ is divisible by $p(n)$.

Source : here

-
Welcome to Math.SE! Since you're new here, I thought I'd mention that we like to see the work you have done in trying to answer you own question--it prevents us from back-tracking and doing unnecessary searching. On a side note more related to your question, you may want to research the prime counting function (often denoted $\pi(n)$), as this is the typical name given to your $p(n)$. – apnorton May 27 '13 at 16:46
@anorton: The prime counting function $\pi(n)$ is the number of primes less than or equal to n. This is not the same as the OP's function. – daniel May 27 '13 at 17:58
@daniel I stand corrected. Sorry. Then $p(n) = \pi(n-1)$, right? – apnorton May 27 '13 at 18:57
@anorton: Right. – daniel May 27 '13 at 18:58

Hint: Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ be a function such that $f(n+1) - f(n) = 0$ or $1$ and $\lim_{n\rightarrow \infty} \frac{ n} { f(n) } \rightarrow \infty$.

Show that the image of $\frac{ n}{f(n) }$ includes all integers greater than $\frac{ 1}{f(1)}$. It will help for you to consider how this function behaves going from $\frac{n}{f(n)}$ to $\frac{n+1} { f(n+1)}$.

Proof: Consider the integer valued function $g(n) = n - k f(n)$, where $k$ is an integer greater than $\frac{1}{f(1)}$. Observe that $g(n+1)-g(n)$ is equal to 1 (if $f(n+1)=f(n)$) or is negative (if $f(n+1) > f(n)$). From the conditions, we get that $g(1)$ is negative, and $g(n)$ is eventually positive for a large enough value of $n$. Hence, there is a value $n^*$ such that $g(n^*) = 0$, which gives us $\frac{n^*}{f(n^*)} = k$.

The reason for presenting the answer this way, is that it has nothing to do with the prime counting function, apart from the properties listed in the hint.

-
I scratched my head over "the image of $\frac{n}{f(n)}$" for a while. You mean the image of the function $g:\mathbb N \to \mathbb R$ defined by $g(n) = \frac{n}{f(n)}$, right? – TonyK May 27 '13 at 18:11
@TonyK Yes. That is what it means. – Calvin Lin May 27 '13 at 18:40
I guess this idea can be shown by induction. If we have n/p(n) = k then for some m we must be able to get m/p(m) = k+1. But my version is verbose. Is there a better way? +1 – daniel May 27 '13 at 21:58
@daniel Certainly. The easiest way I know, is to consider the integer valued function $n - k g(n)$, where $k$ is an integer that's larger than $\frac{1}{f(1)}$. This starts off negative (or 0), and eventually becomes positive. Each step, it either increases by 1 (if $f(n)$ stays constant) or decreases by a bunch (if $f(n)$ increases). Show that there is some value such that $n^* - k g(n^*) = 0$. – Calvin Lin May 27 '13 at 22:01
@karmanaut: I thought Calvin's solution was good and didn't want to distract by posting it--if you like I can try to re-do it and post. Too long for comment. – daniel Jun 2 '13 at 9:55