Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Chen Wang
Chen Wang
  • 243
  • 1
  • 9

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^2\mathbb{Z})^*$$c\in(\mathbb{Z}/m^3\mathbb{Z})^*$ such that $m|C_{km^2+c}$$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+1}-3$$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^2}$$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^2}$$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^2}$$pq+m\equiv c\pmod{m^3}$, and therefore $m|C_{pq+m}$.

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^2\mathbb{Z})^*$ such that $m|C_{km^2+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+1}-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^2}$. 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^2}$ for sufficiently large $p$; we choose such a prime as $q$ to see that $pq+m\equiv c\pmod{m^2}$, and therefore $m|C_{pq+m}$.

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

Source Link
Chen Wang
Chen Wang
  • 243
  • 1
  • 9

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^2\mathbb{Z})^*$ such that $m|C_{km^2+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+1}-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^2}$. 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^2}$ for sufficiently large $p$; we choose such a prime as $q$ to see that $pq+m\equiv c\pmod{m^2}$, and therefore $m|C_{pq+m}$.