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.

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?

share|improve this question
add comment

1 Answer

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