If $n$ is any odd number, prove that $\displaystyle{\sum_{k=1}^{n-1}\frac{(n-1)!}{k} \equiv 0 \pmod{n}}$.

I have a strong feeling that Lagrange's Theorem might be involved somehow, but I can't translate it into any work that seems to lead anywhere.

Thanks for any help!

• @JaideepKhare Sorry. Edited. – John Doe May 4 '17 at 8:15
• Not sure about Lagrange... but the trick that Gauss used to compute $1+2+\ldots+n$ works like a charm here. – darij grinberg May 4 '17 at 8:29

Notice for example that in

$$\frac{6!}{1} + \frac{6!}{2} + \ldots + \frac{6!}{5} + \frac{6!}{6}$$

we have $\frac{6!}{1} + \frac{6!}{6}$ is divisible by seven, $\frac{6!}{2} + \frac{6!}{5}$ is divisible by seven, $\frac{6!}{3} + \frac{6!}{4}$ is divisible by 7.

In general this is true. Note that

$$\frac{(n-1)!}{k} + \frac{(n-1)!}{n-k} = \frac{n!}{k(n-k)}$$

which, we see, is divisible by $n$. This also explains why $n$ has to be odd, so the terms in the sum pair up.

HINT: Let $S(n):=\sum_{k=1}^{n-1}\frac{(n-1)!}{k}$. Then for all $n>1$ some algebra shows that $$S(n+2)=n(n+1)S(n)+(2n+1)\cdot(n-1)!.$$

Similar ideas as above: Let $x = \sum_{k=1}^{n-1}\frac{(n-1)!}{k}$

Then we can rewrite $x = \sum_{k=1}^{n-1}\frac{(n-1)!}{n-k}$

Adding we get $2x = \sum_{k=1}^{n-1}\frac{n!}{k(n-k)} = 0 \mod n$

Since $n$ is odd, $x = 0 \mod n$