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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.