If $n$ is a prime then for all $k$ with $1 \le k \le [n/2]$, $k$ divides ${n-1 \choose 2k-1}$ because of the identity ${n-1 \choose 2k-1} \frac{n}{k}=2{n \choose 2k}$. My question is whether an integer $n$ satisfying the divisibility conditions must be prime ?

This may be interesting because of the identity $ \sum_{k=1}^{[n/2]} {n-1 \choose 2k-1} \frac{1}{k}=(2^n-2)/n,$ which shows that any such composite $n$ must be a Fermat pseudoprime to the base 2 and hence must be quite rare. The sum formula which holds for all $n$ can be deduced from halving the expansion $2^{n}=\sum_{k=0}^{n} {n \choose k}$.

Any such $n$ must be odd, square-free, and at least $10^7$.

What is probably more interesting than this simple result is the way we are led to it by considering the iteration of the map $f(x)=x-1/x$. For each $n$ there are $2^n-2$ points with periods $n$ and since there is no fixed point, for $n$ prime they must form union of $n$ cycles and we know for each $k$ with $1 \le k \le [n/2]$, exactly ${n-1 \choose 2k-1} \frac{1}{k}$ of the cycles intersect the interval $(0,1)$ $k$ times. Since this accounts for all the cycles, we are led to the divisibility condition and the sum formula which also gives a combinatorial proof.

[Added July 31: Extension to base $m>2$] We still have for $n$ prime, $m$ divides ${n-1 \choose mk-1} \frac{1}{k}$ since ${n-1 \choose mk-1} \frac{n}{k}=m {n \choose mk}$ but the sum $\sum_{k=1}^{[n/m]}{n-1 \choose mk-1} \frac{1}{k}$ grows much slower than $(m^n-m)/n$ for $m>2$. The added question is how can one relate the sum to some form of Fermat quotient for $m>2$ ?

It is possible to consider a more general degree $m$ rational map of the form $f(x):=x-\sum_{j=1}^{m-1} \frac{a_j}{x-b_j}$ where $a_j>0$ and $b_j$ are distinct real numbers which has $m^n-2$ points of period $n$. Adding inclusion exclusion, there will be exactly $q_m(n):=\sum_{d|n} \mu(n/d)\frac{(m^n-m)}{n}$ primitive $m$ cycles, where $\mu$ is the Moebius function. However it is not clear if all cycles intersect $(b_1,b_2)$ for $m>2$. Incidently $q_2(n)$ starts as $1,2,3,6,9,18...$ matches some sequences in OEIS which gives many other combinatorial interpretations.


Such an $n$ must be prime. If $\frac{1}{k} \binom{n-1}{2k-1}$ is an integer for all $1 \leq k \leq \lfloor \frac{n}{2} \rfloor$, then $n$ divides $\binom{n}{2k}$ for all $1 \leq k \leq \lfloor \frac{n}{2} \rfloor$.

Suppose that $n$ is odd and squarefree and $p$ is a prime dividing $n$. Then $p$ is odd, and so $n-p$ is even, and we have that $n$ divides $\binom{n}{n-p}$. Assuming that $n$ is odd and squarefree, then for all primes $p | n$, $n-p$ is even. However, we have that $n$ divides $\binom{n}{n-p} = \binom{n}{p} \equiv \frac{n}{p} \pmod{p}$, where the congruence follows from Lucas's theorem. This is a contradiction since $n/p$ is not a multiple of $p$.

  • 3
    $\begingroup$ For the asker's claim - any $n$ satisfying the divisibility conditions must be odd, by looking at the case $k=\frac{n}{2}$ for even $n$, and must be squarefree: taking $k=p$ for any prime $p$ dividing $n$ gives $\nu_p {n-1\choose 2p-1}=\nu_p(n-p)-1$, so $p^2$ divides $n-p$. $\endgroup$ – Zack Wolske Jul 25 '14 at 20:36

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.