Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite
1

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

share|improve this question
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. – 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
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$. – 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

2 Answers

up vote 8 down vote accepted

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

share|improve this answer
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
up vote 1 down vote

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

share|improve this answer
This does not answer my question. – glebovg Oct 3 '12 at 18:15
This is not an answer. Please Provide context for links. – robjohn♦ Oct 3 '12 at 21:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.