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.



A strengthening of base 2 Fermat pseudoprime
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](http://en.wikipedia.org/wiki/Lucas%27_theorem). This is a contradiction since $n/p$ is not a multiple of $p$.


