The condition is $0 < q <p$. This result is a direct consequence of a well-known theorem of Lucas, which states that : If $p$ is a prime, $n,k$ are nonegative integers with base $p$ representations (some digits may be zero, even the leading ones for $k$) $n = n_0 + n_1p + ... + n_tp^t$ and $k = k_0 + k_1p + ... + k_tp^t$ then $C_n^k \equiv \prod_{i = 0}^{t} C_{n_i}^{k_i}$ modmath=inline]$p$[/math. From that theorem, we deduce that $C_n^k$ is divisible by $p$ if and only if $C_{n_i}^{k_i}$ is equal to zero for some $i$, that is $n_i < k_i$ for some $i$. Note that for $0 \leq k \leq n$, we have $k_t \leq n_t$, but for $k = (p-1) + (p-1)p + ... (p-1)p^{t-1}$, if $C_n^k$ is not divisible by $p$ that leads to $n_i = p-1$ for $i = 0,1,...,t-1$ so that, if none of the $C_n^k$ is divisible by $p$, we must have $n = q \times p^t - 1$ for some $q = n_t \in \{0,1,...,p-1\}$. The converse is easy. Pierre.

I just want to point out a solution without using Lucas's theorem or anything tricky. We have \[\binom nk \frac{n-k}{k+1}=\binom n{k+1}\] Suppose $p^s<n\leq p^{s+1}$. Then, no binomial coefficent is a multiple of $p$ iff whenever $p$ divides $n-k$, it also divides $k+1$, and also whenever $p^2$ divides $n-k$ it divides $k+1$ and so on up to whenever $p^s$ divides $n-k$, it divides $k+1$. The last part is true iff $n-k\equiv -(k+1)\mod p^s$, or $n\equiv -1 \pmod p^s$. This is equivalent to the problem statement.

pbornsztein wrote: but for $k = (p-1) + (p-1)p + ... (p-1)p^{t-1}$, if $C_n^k$ is not divisible by $p$ that leads to $n_i = p-1$ for $i = 0,1,...,t-1$ What if $k\neq (p-1) + (p-1)p + ... (p-1)p^{t-1}$?

caffeineboy wrote: whenever $p$ divides $n-k$, it also divides $k+1$, and also whenever $p^2$ divides $n-k$ it divides $k+1$ and so on up to whenever $p^s$ divides $n-k$, it divides $k+1$. The last part is true iff $n-k\equiv -(k+1)\mod p^s$ As far as I'm concerned $\forall_{l\in\lbrace 1,2,...,s\rbrace} \ [p^l|n-k\implies p^l|k+1]$ isn't equivalent to $p^s|(n-k)+(k+1)$