The following open problem was shown to me by Maxim Kontsevich. I
state it in a different but equivalent form. Let $a(n)$ be the sequence
at <http://oeis.org/A131868>, that is,
 $$ a(n) =\frac{1}{2n^2}\sum\_{d|n}(-1)^{n+d}\mu(n/d){2d\choose d}. $$
Is it true that $6a(n)/n$ is always an integer? The sequence begins
(starting at $n=1$) $(1,1,1,2,5,13,35,100,300,925,2915,9386,\dots)$.


If $n$ is prime then the result is true. It is equivalent to
the well-known fact that ${2p\choose p}\equiv 2\,(\mathrm{mod}\,p^3)$
for a prime $p>3$. See for instance *Enumerative Combinatorics*, vol.
1, second ed., Exercise 1.14(d).



A congruence involving binomial coefficients
Let $g(n) = 3(-1)^n\binom{2n}{n}$. The conjecture states $(g \* \mu)(n)$ is divisible by $n^3$. We'll show the divisibility prime-power-wise.


Consider any $p|n$. We can couple summands in $g \* \mu$ as follows: divisors $d\_1,d\_2$ of $n$ are coupled iff $d\_1=pd\_2$ and $\mu(n/d\_1), \mu(n/d\_2)\neq 0$. We can now rewrite $(g \* \mu)(n)$ as a sum over couples: $\sum\_{(d\_1,d\_2)} \mu(n/d\_1) (g(d\_1) - g(d\_2))$. This way we see it is enough to show that $p^{3k} \mid g(dp^k)-g(dp^{k-1})$ for any prime $p$ and $(d,p)=1$.


For $p \ge 5$, this follows directly from the case $\epsilon=0$ of Lemma A in 
[Gessel's Paper](http://people.brandeis.edu/~gessel/homepage/papers/gen-eul.pdf):



> 
> Let $p$ be a prime. Let $\epsilon=1$ if $p$ is 2 or 3, and $\epsilon=0$ if $p$ is greater than $3$. Then $\binom{p^ka}{p^k b} \equiv \binom{p^{k-1}a}{p^{k-1}b} \pmod {p^{3k-\epsilon}}$
> 
> 
> 


This means that the conjecture is true for any $n$ not divisible by $2,3$.


For $p=3$, this also follows from the lemma from the $\epsilon=1$ case, thanks to the fact that the multiplicative term 3 appears in $g$.


So it remains to work out $p=2$. From the same lemma, we find that for $p=2$, $p^{3k-1} \mid g(dp^k)-g(dp^{k-1})$, so $a(n)$ is at worst an half-integer.


The proof of the lemma relied on theorem 2.2. Specializing the theorem to the case $p=2, a=2^{k+1}t,b=2^k t$ we find (using the fact that $v\_{2}(\binom{2n}{n}) \ge 1$):



> 
> If $t$ is odd and $k\ge 2$, $\binom{2^{k+1}t}{2^{k}t} \equiv \binom{2^k t}{2^{k-1}t} \pmod {2^{3k}}$. If $t$ is odd and $k=1$, $\binom{2^{k+1}t}{2^{k}t} \equiv -\binom{2^k t}{2^{k-1}t} \pmod {2^{3k}}$
> 
> 
> 


So $g(2^k t) \equiv g(2^{k-1}t) \pmod {2^{3k}}$ (only in the case $k=1$ we used the $(-1)^n$ term in $g(n)$). Hence the conjecture is proved.


