6
$\begingroup$

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

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

  • 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 is not an answer. Please [Provide context for links](http://math.stackexchange.com/questions/how-to-answer).2012-10-03