Can any one explain why the probability that an integer is divisible by a prime $p$ (or any integer) is $1/p$?
Probability that an integer is divisible by a prime $p$
-
4One critical caveat: while the heart of the statement is true, using 'probability' over the integers is fraught with peril, since there's no uniform probability distribution available to define a probability with respect to. – 2012-10-03
-
0@StevenStadnicki But there must be a reason why we define the probability in this way, correct? Some heuristic argument perhaps? – 2012-10-03
-
0glebovg See my answer for the details - the most straightforward way of defining such a probability is known as the 'natural density'. – 2012-10-03
-
1There is no "uniform" probability on the integers. You can define it as the limit of $p_n$, where $p_n$ is the probability that a uniform random integer from $1$ to $n$ is divisible by $p$. – 2012-10-03
-
0Note, under these definitions, you don't need $p$ prime, it's true that the density of numbers divisible by $d$ is $\frac{1}{d}$ for any positive integer $d$. – 2012-10-03
2 Answers
As I said in a comment, the notion of 'probability' over the set of all integers (or equivalently, the natural numbers) is fraught with some peril. A better statement of the question is that the natural density of the numbers divisible by $p$ is $\frac{1}{p}$. Natural density captures what people think of as probability; it simply represents the limit of the proportion of integers with the given property. More specifically, the natural density of a set $A$ is defined as the limit $\lim_{n\rightarrow\infty}\frac{1}{n}\#\left\{i:i\leq n \wedge i\in A\right\}$. For more details, see http://en.wikipedia.org/wiki/Natural_density.
In your particular case, the natural density result is easy to prove: the number of naturals $i\leq n$ that are divisible by $p$ (call this count $c$) satisfies $\frac{n}{p}-1\lt c\lt \frac{n}{p}+1$, so the density $d = \lim_{n\rightarrow\infty}\frac{c}{n}$ satisfies $\frac{1}{p}-\frac{1}{n}\lt d\lt \frac{1}{p}+\frac{1}{n}$ for all $n$; therefore we must have $d=\frac{1}{p}$.
-
0Great answer, but how would I apply this argument to show that the "probability" of a natural number from a set $\{1,2, \ldots ,M\}$ is about $1/\ln (M)$ using PNT? – 2012-10-05
-
0glebovg Well, by the PNT there are roughly $M/\ln(M)$ primes less than $M$, so just dividing that by $M$ gives the probability that a number from that set is prime... (and shows that the density of the primes is 0, which I presume is the result you're ultimately after.) – 2012-10-08
-
0Can you give a proof of the claim that $n/p - 1 < c < n/p + 1$? – 2018-02-03
-
1@aortiz it's essentially trivial. There are exactly $s$ of them $\leq sp$, so if $sp\leq n \leq (s+1)p$... – 2018-02-03
-
0This does not answer my question. – 2012-10-03
-
0This is not an answer. Please [Provide context for links](http://math.stackexchange.com/questions/how-to-answer). – 2012-10-03