# A divisibility problem involving Catalan numbers

The Catalan numbers in combinatorics are given by $$C_n=\frac1{n+1}\binom{2n}n=\binom{2n}n-\binom{2n}{n+1}\ \ (n=0,1,2,\ldots).$$

In 2014 I formulated the following conjecture.

Conjecture. For each $$m=1,2,3,\ldots$$, there is a positive integer $$n$$ such that $$\gcd(m,n)=1$$ and $$mn\mid C_{m+n}$$.

See http://oeis.org/A248123 for related data. For example, $$\gcd (4,21)=1$$, and $$4\times 21$$ divides $$C_{4\times 21}=4861946401452$$.

QUESTION: Is the above conjecture true? If true, how to prove it?

This conjecture is true. The way to prove it is to choose $$n=pq$$ as a product of two large primes.
We first point out that $$pq|C_{pq+m}$$ if we choose $$p>m+1$$ and $$q\in(3p/2,2p)$$; this follows from standard divisibility results of binomial coefficients.
Therefore, what's left is to choose $$p$$ and $$q$$ in a way such that $$m|C_{pq+m}$$. This can be done by the following lemma:
Lemma. For any $$m\in\mathbb{Z}^+$$, there exists $$c\in(\mathbb{Z}/m^3\mathbb{Z})^*$$ such that $$m|C_{km^3+c}$$ for all $$k\in\mathbb{Z}_{\geq0}$$.
Proof of the lemma. Using CRT we can reduce the problem to the case of prime powers $$m=\ell^k$$. Here $$c=\ell^{k+2}-3$$ for $$\ell=2$$ and $$c=\ell^{k+1}-2$$ for $$\ell\geq3$$ is a valid choice for all prime powers $$\ell^k$$. (We look again at divisibility properties of binomial coefficients!)
Armed with the existence of such a $$c$$, we choose a sufficient large prime $$p$$ such that $$p\equiv1\pmod{m^3}$$. Note that the prime number theorem on arithmetic progressions implies that the interval $$(3p/2,2p)$$ contains a prime congruent to $$c-m\pmod{m^3}$$ for sufficiently large $$p$$; we choose such a prime as $$q$$ to see that $$pq+m\equiv c\pmod{m^3}$$, and therefore $$m|C_{pq+m}$$.