3
$\begingroup$

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

1 Answers 1

7

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.

  • 0
    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.2010-10-19