# Probability that an integer is divisible by a prime $p$

Can any one explain why the probability that an integer is divisible by a prime $p$ (or any integer) is $1/p$?

-
One 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. – Steven Stadnicki Oct 3 '12 at 18:15
@StevenStadnicki But there must be a reason why we define the probability in this way, correct? Some heuristic argument perhaps? – glebovg Oct 3 '12 at 18:18
glebovg See my answer for the details - the most straightforward way of defining such a probability is known as the 'natural density'. – Steven Stadnicki Oct 3 '12 at 18:25
There 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$. – Thomas Andrews Oct 3 '12 at 18:25
Note, 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$. – Thomas Andrews Oct 3 '12 at 19:37

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}$.
Great 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? – glebovg Oct 5 '12 at 23:01
glebovg 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.) – Steven Stadnicki Oct 8 '12 at 18:01