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

I think I might have asked this question before, but I can't find it on the site, so I sincerely apologize if I am making a duplicate. But anyway, I have been working on this proof for several weeks and am stumped.

If $\pi(x)$ is the number of primes less than or equal to $x$, prove that $$\lim_{x\to\infty}\frac{\pi(x)}{x} = 0.$$

I have this:

So far I know that prime numbers can only be (if greater than $k$ for $p \pmod{k}$:

• $1 \pmod{2}$.

• $1,2 \pmod{3} \Rightarrow$ upper bound of $\frac{\pi(x)}{x}$ is $\frac{2}{3}$.

• $1,3 \pmod {4}$.

• $1,2,3,4 \pmod{5}$.

• $1,5 \pmod{6}\Rightarrow$ upper bound of $\pi(x)/x$ is $\frac{1}{3}$.

• $1,2,3,4,5,6 \pmod{7}$.

• $1,3,5,7\pmod{8}$.

• $1,2,4,5,7,8\pmod{9}$.

Any number prime $p \pmod{k}$ can only have a remainders that are relatively prime to $k$, as a number would not be prime if it could be expressed as a composite plus a factor of that composite. And I know that these possible remainders demonstrate a fraction of the possible numbers that can be prime, given that in any range of numbers there must be at least one that satisfies each possible remainder $\pmod{k}$. ...

But I'm not sure what I can conclude from this. I think that I need to find a way to express a number $N$ with respect to a prime $p$ such that $p \pmod N$ has a constant number of possible values, $K$. Then as $N$ increases, $K/N \to 0$. But otherwise I'm really stumped where to go.

I have considered the following: multiplying all prime numbers less than an arbitrary value and modding by that, so there are no relative primes less than a certain value except 1. But the problem with this is once you reach a certain value there can be a multiple of this as $2p_1p_2\cdots p_n$. So I don't think that works.

Any help would be much appreciated! Also, this is a first-semester number theory class, so I don't have much math knowledge to work with. I've done calc A,B,C, linear algebra A, and this number theory class.

• I don't see a clear question (the question should be stated clearly in the body of your post), and I don't see how discussing the congruence classes of primes relates to your title. $\pi(x)$ is, usually, the number of primes less than or equal to $x$. So $\pi(x)/x$ represents the "fraction" of numbers that are prime and less than or equal to $x$. It is known that $\lim((\pi(x)/x)/(\ln x/x)) = 1$ (the "Prime Number Theorem"), so that shows the numerator must converge to $0$ (since the denominator does). But what is the "inf"? Do you mean the limit inferior? Also, try to use some mark-up... Mar 22, 2011 at 18:40
• @Arturo, it seems to me that Ross is asking for an elementary proof of that.
– lhf
Mar 22, 2011 at 18:43
• @lhf: Hard to see, since it's not stated in the post; and I don't really see how the discussion of primes in arithmetic progressions relates. And I just finally figured out that "inf" is supposed to be $\infty$... Sigh. Mar 22, 2011 at 18:45
• How do you go from the fact that (other than $p=3$) a prime must be congruent to $1$ or $2$ modulo $3$ to claiming that primes have density at most $0.5$? Shouldn't that be $2/3$? Mar 22, 2011 at 18:55
• There is a proof of this in Ireland and Rosen based on estimating the sum of the logs of primes in terms of the binomial coefficient 2n choose n. Mar 22, 2011 at 19:02

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

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

• @Ross: Let me know if this gets you all the way, or if you need me to explain a bit better (or more). It's a nice approach, and it can even be refined to get your closer to the Prime Number Theorem. Mar 22, 2011 at 20:04
• LeVeque in Fundamentals of Number Theory (section 6.5) has this: $$\prod_{p\le x} 1-\frac{1}{p} < \frac{1}{\log x}$$ from which he deduces $$\pi(x) \ll \frac{x}{\log \log x}$$
– lhf
Mar 22, 2011 at 20:46
• @lhf: Yes, the first inequality is where I'm leading, and why I say you can refine it to get you closer to the PNT. Mar 22, 2011 at 20:53
• Dear Arturo, regarding the previous two comments, you wrote $\lim_{n \to \infty} \pi(x)/x$, but you mean $\lim_{x \to \infty}\pi(x)/x$. I think this was the source of @Zach's confusion. Regards, Mar 23, 2011 at 4:25
• @lhf , @Arturo: You might find constant to be a little interesting as well. It is one of Mertens formulas which tells us $$\prod_{p\leq x}\left(1-\frac{1}{p}\right)^{-1}=e^\gamma \log x +O(1)$$ so that $$\prod_{p\leq x}\left(1-\frac{1}{p}\right) = \frac{e^{-\gamma}}{\log x}+O\left(\frac{1}{\log x}\right),$$ where $\gamma$ is Eulers Constant. The error term can be improved to $$O\left(e^{-c\sqrt{\log x}}\right)$$ under the prime number theorem. Mar 23, 2011 at 14:57

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

• I have just one question about this. Why do you need the summation of 1/p? I don't see why the first parts with the product of (1-1/p) is insufficient. (I assume that the uppercase sigma is product notation?)
– user7435
Mar 22, 2011 at 19:24
• @Ross: Taking $\log$ on the Products
– anonymous
Mar 22, 2011 at 19:30
• What do you mean?
– user7435
Mar 22, 2011 at 19:57
• $\log (1-1/p) \approx - 1/p$ since the derivative of $\log x$ at $x=1$ is $1$. That the product diverges to $0$ is the same as that the sum of the reciprocals of the primes diverges to $\infty$. Mar 24, 2011 at 6:43
• So you show that if you have more primes then you have fewer primes! (Which makes sense because each prime prevents other numbers from being prime). Aug 22 at 19:57

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.

• You need another idea than that there are infinitely many primes. There are infinite sequences of primes such that $\prod \frac{p_i-1}{p_i} \ne 0$. . Mar 22, 2011 at 23:04
• What you can do is use the assumption that $\pi(x)/x$ does not go to zero, that is that the probability that $n$ is prime is at least some $p > 0$. Mar 22, 2011 at 23:21