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}$.
