# [number theory] prove that lim x->infinity pi(x)/x=0

Let's try something else.

If a number from 0 .. N is not prime it will have a factor (not necessary a prime number) lower than $$\sqrt{}N$$.

If we take the numbers from 1 to $$\sqrt{}N$$ and multiply them with numbers from 2 to $$\sqrt{}N$$ we will get $$\sqrt{}N$$ * ($$\sqrt{}N$$ - 1) = N - $$\sqrt{}N$$ numbers which have a factor lower than $$\sqrt{}N$$.

So the probability to pick a number which has a factor lower than $$\sqrt{}N$$ is somehow greater than (N - $$\sqrt{}N$$)/N, but we are looking for numbers that are prime and don't have a factor lower than $$\sqrt{}N$$. Our probability will be therefore lower than 1 - (N - $$\sqrt{}N$$)/N = $$\sqrt{}N$$/N which becomes 0 as N -> infinity.

Maybe you can turn this argument into a proof.

Last edited:
Hurkyl
Staff Emeritus
Gold Member
I think I'm close. I have condensed our previous conversation into the following:

Any number prime p (mod 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 (mod k). ...
And you even have a formula for that fraction. (invoking number-theoretic functions)

But I'm not sure what I can conclude from this.
You can conclude that the limit is no bigger than every possible fraction that can appear in the analysis above.

(Note that you can compute the limit of interest if you can show the limit is less than or equal to every positive number)