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.

  • 1
    $\begingroup$ 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... $\endgroup$ Mar 22, 2011 at 18:40
  • 2
    $\begingroup$ @Arturo, it seems to me that Ross is asking for an elementary proof of that. $\endgroup$
    – lhf
    Mar 22, 2011 at 18:43
  • $\begingroup$ @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. $\endgroup$ Mar 22, 2011 at 18:45
  • 2
    $\begingroup$ 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$? $\endgroup$ Mar 22, 2011 at 18:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – quanta
    Mar 22, 2011 at 19:02

3 Answers 3


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

  • $\begingroup$ @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. $\endgroup$ Mar 22, 2011 at 20:04
  • 1
    $\begingroup$ 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}$$ $\endgroup$
    – lhf
    Mar 22, 2011 at 20:46
  • $\begingroup$ @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. $\endgroup$ Mar 22, 2011 at 20:53
  • 1
    $\begingroup$ 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, $\endgroup$
    – Matt E
    Mar 23, 2011 at 4:25
  • 1
    $\begingroup$ @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. $\endgroup$ 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.)

  • $\begingroup$ 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?) $\endgroup$
    – user7435
    Mar 22, 2011 at 19:24
  • $\begingroup$ @Ross: Taking $\log$ on the Products $\endgroup$
    – anonymous
    Mar 22, 2011 at 19:30
  • 1
    $\begingroup$ What do you mean? $\endgroup$
    – user7435
    Mar 22, 2011 at 19:57
  • 4
    $\begingroup$ $\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$. $\endgroup$ Mar 24, 2011 at 6:43
  • $\begingroup$ 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). $\endgroup$
    – gnasher729
    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.

  • $\begingroup$ 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$. . $\endgroup$ Mar 22, 2011 at 23:04
  • $\begingroup$ 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$. $\endgroup$ Mar 22, 2011 at 23:21

You must log in to answer this question.