Does there exist a probability distribution on $\mathbb{Z}$ such that
for every integer $n\geq 1$, the probability that a random integer $x$
is divisible by $n$ equals $1/n$?


Henry Cohn has an argument why this is not possible, but it is not
completely rigorous. First, it is easy to see that we can assume that
the distribution is supported on the positive integers. Let $p\_n$ be
the probability of $n$. For any function $f$ on the positive integers
for which we get convergence, we have (by the assumption on $p\_n$)
 $$ \sum\_k p\_k\sum\_{n|k}f(n) = \sum\_n \frac{f(n)}{n}. $$
Let $g(k)=\sum\_{n|k} f(n)$. By Möbius inversion,
$f(n) = \sum\_{k|n}g(k)\mu(n/k)$. Writing $n=mk$, the first equation
becomes
 $$ \sum\_k p\_k g(k) =\sum\_k g(k)\sum\_m \frac{\mu(m)}{mk}. $$
This should hold for all $g$ for which $\sum\_n f(n)/n$ converges
absolutely, so it should follow that
 $$ p\_k = \frac 1k\sum\_m \frac{\mu(m)}{m}. $$
This is nonsense since first of all, $\sum\_m \mu(m)/m =0$ (equivalent
to the prime number theorem), and even if we didn't know that, there's
no way $p\_k$ can be proportional to $1/k$ since $\sum 1/k=\infty$.


This argument is not completely rigorous since we have interchanged
sums and equated coefficients of $g(k)$ without justification. It's
also a problem that $\sum\_m \mu(m)/m$ is conditionally convergent.



Existence of a "quasi-uniform" probability distribution on $\mathbb{Z}$
No. Let's restrict our attention to $\mathbb{N}$. The hypotheses imply that if $q$ is a prime, then the probability that a random positive integer is not divisible by $q$ is $1 - \frac{1}{q}$. They also imply that these events are independent. Now let $n$ be a positive integer. If $q\_1, q\_2, \dots$ is an enumeration of the primes not dividing $n$ it follows that


$$p\_n \le \prod\_{i=1}^m \left( 1 - \frac{1}{q\_i} \right)$$


for all $m$. But taking $m \to \infty$ the RHS approaches $0$; contradiction. Note that this argument does not require the prime number theorem; we just need to know that the harmonic series diverges.


**Edit:** Here is a generalization which more completely rescues Henry Cohn's argument. Generalize the condition to being that the probability of a positive integer being divisible by $n$ is $\frac{1}{n^s}$, for some real number $s > 0$. This is equivalent to requiring that the probability is 1) multiplicative in $n$ and 2) monotonically decreasing.


It follows that if $q$ is prime, then the probability that the exponent of $q$ in the prime factorization of a random positive integer is exactly $k$ is


$$\frac{1}{q^{ks}} - \frac{1}{q^{(k+1)s}} = \frac{1}{q^{ks}} \left( 1 - \frac{1}{q^s} \right).$$


We again have that for different primes $q$ these events are independent. Now, if $q\_1, q\_2, \dots$ is an enumeration of the primes and $n = \prod q\_i^{k\_i}$ is a positive integer, it follows that


$$p\_n \le \prod\_{i=1}^m \frac{1}{q\_i^{k\_i s}} \left( 1 - \frac{1}{q\_i^s} \right).$$


for all $m$. If $s \le 1$ then the RHS converges to $0$ as $m \to \infty$ (this, again, does not require the prime number theorem) and we get a contradiction. If $s > 1$ then the RHS converges to


$$p\_n = \frac{1}{n^s \zeta(s)}$$


and this is an equality because the RHS is the probability that a random positive integer has the same prime factorization as $n$. 


There is a straightforward generalization where $\mathbb{N}$ is replaced by the set of nonzero ideals in the ring of integers $\mathcal{O}\_K$ of a number field $K$ and the probability of an ideal being divisible by an ideal $I$ is $\frac{1}{N(I)^s}$, where we get the Dedekind zeta function instead. 


