prove that $\lim_{x\to\infty} \pi(x)/x=0$

Solution 1:

There are a lot of approaches that can be used to establish this, but I'll try to stick to pushing your own idea through. I'm going to introduce a bit of notation first:

If we let $\varphi(n)$ be the number of positive integers less than or equal to $n$ that are relatively prime to $n$, you are saying that since for any given $n$ primes must fall among the $\varphi(n)$ congruence classes relatively prime to $n$ (except perhaps for the finite number of primes that divide $n$, and those don't affect the eventual distribution), that shows that the density of primes is at most $\frac{\varphi(n)}{n}$ for every $n$. That is, $$\lim_{x\to\infty}\frac{\pi(x)}{x} \leq \frac{\varphi(n)}{n}\quad\text{for all }n;$$ so it suffices to show that $$\inf\left\{\left.\frac{\varphi(n)}{n}\right|\; n\geq 0\right\} = 0.$$ For this, it is enough to show that $\liminf\frac{\varphi(n)}{n} = 0$.

This approach can work, though, and it can be done precisely by focusing on the integers $n$ that are "the product of all primes up to some $N$", so you are definitely on the right track and very close.

(I don't know if you can construct a sequence of numbers $N_k$ such that $\varphi(N_k)$ is constant and $N_k\to\infty$ as $k\to\infty$, which is what you say you want to do in your paragraph that begins "But I'm not sure what I can conclude from this..."; frankly, I doubt it can be done easily. Or at least, I can't think of a way to do it. Added: In fact, for every $K$, there is at most finitely many $n$ for which $\varphi(n)\leq K$; see below the break).

One way to push it through all the way it is to consider the following formula for $\varphi(n)$: $$\varphi(n) = n\prod_{\stackrel{p|n}{p\text{ prime}}} \left(1 - \frac{1}{p}\right).$$ Verify that this is true.

This means that $$\frac{\varphi(n)}{n} = \prod_{\stackrel{p|n}{p\text{ prime}}}\left(1 - \frac{1}{p}\right).$$

Now, pick $n$ to be "the product of all primes up to $N$", for some $N$. We're going to show that for the sequence we get from these very special $n$, we have $\lim\limits_{n\to\infty}\frac{\varphi(n)}{n} = 0$, which will show what we want to show.

For such an $n$ we have $$\frac{\varphi(n)}{n} = \prod_{\stackrel{p|n}{p\text{ prime}}}\left(1 - \frac{1}{p}\right) = \prod_{\stackrel{p\leq N}{p\text{ prime}}}\left(1 - \frac{1}{p}\right).$$ So it will suffice to show that $$\lim_{N\to\infty} \prod_{\stackrel{p\leq N}{p\text{ prime}}}\left(1 - \frac{1}{p}\right) = 0.$$

There are two pieces of information, both from Calculus, that you can use to establish this. First: if $|r|\lt 1$, then $$\frac{1}{1-r} = 1 + r + r^2 + r^3 + \cdots + r^n + \cdots$$ and in particular, if $p$ is prime, then $$\frac{1}{1 - \frac{1}{p}} = 1 + \frac{1}{p} + \frac{1}{p^2} + \cdots + \frac{1}{p^n} + \cdots.$$

The second piece of information is an upper bound for the integral $\int_1^k\frac{du}{u}$. Since $y = \frac{1}{u}$ is strictly decreasing, dividing the interval $[1,k]$ into $k-1$ equal parts and taking a left hand sum estimate gives that $$\int_1^k\frac{du}{u} \lt 1 + \frac{1}{2} + \cdots + \frac{1}{k-1}.$$

Finally, one last trick: instead of looking at $$\prod_{\stackrel{p\leq N}{p\text{ prime}}}\left(1 - \frac{1}{p}\right),$$ look at its reciprocal: $$\frac{1}{\prod\limits_{\stackrel{p\leq N}{p\text{ prime}}}\left(1 - \frac{1}{p}\right)} = \prod_{\stackrel{p\leq N}{p\text{ prime}}}\frac{1}{1 - \frac{1}{p}} = \prod_{\stackrel{p\leq N}{p\text{ prime}}}\left(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots + \frac{1}{p^k} + \cdots\right).$$

See if you can show that this is greater than or equal to a quantity which you know goes to $\infty$ as $N\to\infty$ (say, by considering the integral I mentioned above). Then you can leverage that to show the limit inferior of $\frac{\varphi(n)}{n}$ is indeed equal to $0$.

Added. In fact, for every $K\gt 0$ there are at most finitely many integers $n$ such that $\varphi(n)\leq K$, so your idea of trying to find a sequence going to $\infty$ for which $\varphi(n)$ always equals $K$ cannot prosper, I'm fraid.

To see this, note that $\varphi(n)$ is multiplicative: if $\gcd(a,b)=1$, then $\varphi(ab) = \varphi(a)\varphi(b)$. Also, if $p$ is a prime, then $\varphi(p^r) = (p-1)p^{r-1}$. This completely determines the value of $\varphi$ for any $n$, if you know the prime factorization of $n$.

Now fix $K$. If $n$ is divisible by any prime $p$ with $p\gt K+1$, then $\varphi(n)\geq \varphi(p) = p-1\gt K$. If $p$ is a prime with $p\lt K+1$, then if $r$ is such that $p^{r-1}\gt K$, then $\varphi(p^r)=(p-1)p^{r-1}\geq p^{r-1}\gt K$, so any integer divisible $n$ by at least $p^r$ will have $\varphi(n)\gt K$ as well. So any integer $n$ such that $\varphi(n)\leq K$ must be divisible only by primes less than or equal to $K+1$, and for each such prime there is a largest power that can divide $n$. This means that there are only finitely many $n$ for which $\varphi(n)\leq K$.

Solution 2:

Suppose that you have primes $p_1,..,p_n$. Then only a $$\prod (1-1/p_i)$$ fraction of numbers are divisible by none of the $p_i$. So in particular if $$\prod_p (1-1/p) \to 0$$ we are done. On the other hand, if $\lim\sup \frac{\pi(x)}{x}$ were bigger than $0$, this could not be the case.

We equivalently need $$\sum_p 1/p = \infty$$

Suppose that for some constant $c>0$ and infinitely many $n$ that $\pi(x)/x > c$ Then for infinitely many $x$ there are at least $cx/2$ primes between $cx/2$ and $x$. The sum of the reciprocals of those primes is therefore at least $c/2$ But if we do this for $x_1, x_2, ... $with $x_n > 2/c x_{n-1}$, the primes we find are all distinct therefore the sum of $1/p$ has infinitely many contributions of $c/2$ and thus diverges.

You may want to see this link. See Page 13, Corollary 2. (It's from the book Wladyslaw Narkiewicz: The Development of Prime Number Theory: From Euclid to Hardy and Littlewood.)

Solution 3:

The key is to show that the probability that $n$ is prime goes to zero as $n$ goes to $\infty$. This can be done in several ways, but here is how I would proceed:

If $n \ge 2$, we have a $1/2$ chance that $2 | n$. If $n \ge 6$, we have a $1/2$ chance that $2 | n$, a $1/3$ chance that $3 | n$, and a $1/6$ chance that $6 | n$ (which is the same as saying that $2 | n$ and $3 | n$), so we have a $1/2 + 1/3 - 1/6 = 2/3$ chance that either $2 | n$ or $3 | n$. Keeping in mind that there are infinitely many primes, you should be able to continue in this manner to show that the probability of $n$ being divisible by some prime goes to $0$ as $n$ goes to infinity.