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

  • Thread starter RossH
  • Start date
  • #26
70
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 [tex]\sqrt{}N[/tex].

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

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

Maybe you can turn this argument into a proof.
 
Last edited:
  • #27
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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)
 

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

Replies
11
Views
6K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
6
Views
2K
Replies
23
Views
6K
Replies
2
Views
4K
  • Last Post
Replies
2
Views
21K
Replies
8
Views
10K
  • Last Post
Replies
2
Views
5K
Top