The classical Catalan numbers are given by $C\_n=\frac1{n+1}\binom{2n}n$, for which there is a plethora of generalizations of interpretations in the literature. Still, let us consider one more such:
$$C\_n(k):=\binom{kn}{n,\dots,n}\prod\_{j=0}^{k-1}\frac1{jn+1};$$
where the multinomial coefficient is simply $\frac{(kn)!}{n!^k}$.


**Note.** $C\_n(2)=C\_n$.


The following has been rediscovered many times and it is easy to prove: $C\_n$ is odd iff $n=2^m-1$ for some $m$ (for example, [see this paper](https://arxiv.org/pdf/math/0601339.pdf) by Postnikov and Sagan).


Such considerations prompted me to ask:



> 
> **Question.** Fix a prime $p$. Is this characterization valid?
>  $$\text{$C\_n(p)$ is not divisible by $p$ iff $n=1+p+\cdots+p^m$ for some $m$}.$$
> 
> 
> 


**UPDATE.** Both solutions are great, in particular, I appreciated the variation of techniques that went into them.



Another extension of Catalan: divisibility
Here's a slightly different way to look at this. We have
$$C\_n(k)=\prod\_{j=1}^{k}\left(\frac{1}{(j-1)n+1}\binom{jn}{n}\right).$$
And each factor 
$$\frac{1}{(j-1)n+1}\binom{jn}{n}=\binom{jn}{n}-(j-1)\binom{jn}{n-1}$$
is an integer. For $C\_n(p)$ let us look at the last factor $\frac{1}{(p-1)n+1}\binom{pn}{n}$. Since $\binom{pn}{n}$ is always divisible by $p$ we can say that if $C\_n(p)$ is not divisible by $p$ then $p$ must divide $(p-1)n+1$, or in other words $n$ must be $1\pmod{p}$. If $n$ is written as $a\_r\cdots a\_1a\_0$ in base $p$ then we have $a\_0=1$ and by Lucas's theorem
$$\binom{pn}{n-1}\equiv \prod\_{i=1}^{r}\binom{a\_{i-1}}{a\_{i}}\pmod{p}$$
Therefore in order for $\frac{1}{(p-1)n+1}\binom{pn}{n}$ not to be divisible by $p$ we must have $\binom{a\_{i-1}}{a\_{i}}\neq 0 \pmod{p}$. Therefore $1=a\_0\geq a\_1\geq \cdots \geq a\_r$ which implies that all $a\_i=1$. This is equivalent to saying $n=1+p+\cdots+p^r$ for some $r$. This also takes care of the other factors since for such $n$ we have $$\binom{jn}{n}\equiv j^r\neq 0 \pmod{p}.$$


