Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

More specifically, assume that $d$ is taken from $[1, 2^n]$ and $m$ is taken from $[1, n]$. What is an upper bound on the probability that $d$ is a multiple of $m$?

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

Fixing $m$, the probability that $d$ is a multiple of $m$ is approximately $1/m$. Now, if you choose $m$ randomly from $[1,n]$, and average $1/m$, you get $\frac{1}{n} \sum_{m=1}^n \frac{1}{m}$, which is approximately $\frac{\log n}{n}$.

EDIT: I didn't read the question carefully enough. Sorry.

The least common multiple of the first $n$ numbers grows like $e^n$. So if you take the lcm of the numbers $1 \ldots n \cdot ln 2$, you get a number somewhere around $2^n$ which is going to have as factors all the numbers between $1$ and $n \cdot \ln 2 $. This shows the probability you're interested in is at least $\ln 2$. In fact, this lcm is going to contain as a factor all numbers except prime powers larger than $n \cdot \ln 2$. Since any prime has at most one power in this interval, then by the prime number theorem, you then get a lower bound for the probability of around $1-1/\ln n$. I expect the upper bound matches, but offhand I don't see how to prove it.

share|cite|improve this answer
What about if d is not random, but possibly chosen pathologically? For example, if d were allowed to be chosen from [1, n!], we could let d = n! and then the probability that d mod m = 0 would be 1. – jonderry Oct 19 '10 at 22:39

Your Answer


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.