3
$\begingroup$

I'm learning some number theory and I can't seem to understand why this is the case.

2 Answers 2

3

You ought to specify a distribution before you ask a question like this, because there is no uniform distribution on all of the natural numbers, so there is no particularly natural choice.

However, what we can say is that if you take a large interval of natural numbers, and take a uniform distribution on them, the probability that a given number is a multiple of $m$ is roughly $1/m$. To see this, simply observe that it is equivalent to it being $0\mod m$, and there are $m$ things that you can be mod $m$, so any distribution in which they will be equally likely will give $1/m$ as the probability of any one.

  • 0
    @daniel: I was speaking kind of informally. I mean if you have a random variable that takes each value from the set I specified (a large interval of natural numbers) with equal probability.2012-07-11
5

The probability that $p$ is a factor of $n$, $1\leq n \leq kp$, is $ P_k = \frac {\lvert \{p, 2p, \dotsc, kp \} \rvert} {\lvert \{1, 2, \dotsc, kp \} \rvert} = \frac k {kp} = \frac 1 p $ So the probability that $p$ is a factor of $n\in \mathbb N$ is $ \lim_k P_k = \frac 1 p $