# A strengthening of base 2 Fermat pseudoprime

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$.
• 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$. – Zack Wolske Jul 25 '14 at 20:36