Possible Duplicate:
Prove fingerprinting

Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that $$\text{prob}(a \equiv b \pmod{p}) \le c \ln(n)/(n^{c-1}).$$

Hint: As a consequence of the prime number theorem, exactly $n/ \ln(n) \pm O(n/\ln(n))$ many numbers from $\{ 1, \ldots, n \}$ are prime.

Conclusion: we can compress $n$ bits to $O(\log(n))$ bits and get a quite small false-positive rate.


Browse other questions tagged or ask your own question.