# 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

## 1 Answer

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.

• can you explain this a bit? – Zoltan May 19 '13 at 23:56
• Sure, if only you explain which part(s) you want to see explained a bit. – Did May 20 '13 at 7:24
• How did you make the jump to use a Fourier transformation to begin with? Is this some standard technique that I somehow missed? – Zoltan May 27 '13 at 15:15
• It all depends what one calls standard. Well known by the experts, sure, and advertised several times by Gowers (and others), hence, as such, worth knowing. But standard as in "explained in every calculus textbook", maybe not. – Did May 27 '13 at 19:02