Take the 2-minute tour ×
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.

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

share|improve this question
add comment

2 Answers 2

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|improve this answer
2  
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
add comment

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|improve this answer
add comment

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.