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