# For an arbitrary positive integer d and random modulus m, what is the probability that d mod m = 0?

More specifically, assume d 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?

-

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