6
$\begingroup$

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

  • 4
    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.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
  • 0
    glebovg See my answer for the details - the most straightforward way of defining such a probability is known as the 'natural density'.2012-10-03
  • 1
    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$.2012-10-03
  • 0
    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$.2012-10-03

2 Answers 2

11

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}$.

  • 0
    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?2012-10-05
  • 0
    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.)2012-10-08
  • 0
    Can 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
2

See http://en.wikipedia.org/wiki/Coprime_integers#Probabilities.

  • 0
    This does not answer my question.2012-10-03
  • 0
    This is not an answer. Please [Provide context for links](http://math.stackexchange.com/questions/how-to-answer).2012-10-03