# probability of divisibility

Let S be the sum of k randomly selected integers between 1 and n.

What is the probability of S being divisible q?

Can this be expressed in a closed form?

This is the generalization of one of the problems from this year's hungarian high school final exam - advanced mathematics.

• Is $q$ prime perhaps? – vadim123 May 16 '13 at 17:42
• what is $q$? Is it a prime? You should specify and maybe show where you got so far. – sigmatau May 16 '13 at 17:43
• q is an arbitrary integer between 1 and n. With this general case I have no idea how to start, sadly. – Zoltan May 16 '13 at 17:57
• The problem becomes easy if k is big enough for using CLT. And for $n>>q$ we can even think that $n=q$. Otherwise, if you want the precise formula, the probability should be expressed as the sum of partitions. It gonna be a terrifying formula. – gukoff May 16 '13 at 18:16
• Are there any bounds on $k$? – leeabarnett May 16 '13 at 18:34

One can use discrete Fourier transform, starting with $z=\mathrm e^{2\mathrm i\pi/q}$ a $q$th root of unity and using the identity $$\sum_{u=1}^qz^{un}=q\,\mathbf 1_{q\ \text{divides}\ n}.$$ Thus, $$P[q\ \text{divides}\ S]=\frac1q\sum_{u=1}^qE[z^{uS}].$$ Now, for every $x$, $E[x^S]=E[x^X]^k$ where $X$ is uniform on $\{1,2,\ldots,n\}$, and, for every $x\ne1$, $$E[x^X]=\frac1n\sum_{u=1}^nx^u=\frac{x}n\frac{1-x^n}{1-x},$$ and whether the formula for $P[q\ \text{divides}\ S]$ all this, when put together, yields, is a "closed form" or not is... well, debatable.