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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
I don't understand the phrase "take a uniform distribution." – daniel Jul 11 '12 at 8:51
@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. – Ben Millwood Jul 11 '12 at 22:25

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

share|cite|improve this answer

Your Answer


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