Another generalization of parity of Catalan numbers

Question

Recently, a question by T. Amdeberhan gathered up many enjoyable proofs that a Catalan number $C_n$ is odd if and only if $n=2^r-1$.

Noam D. Elkies' answer considered $F=\sum_{n=0}^\infty C_n x^{n+1}$. Using the facts that this generating function satisfies $F=x+F^2$, and that $(a+b)^{2^m} \equiv a^{2^m}+b^{2^m} \pmod 2$, he showed that

$$F \equiv x+x^2+x^4+x^8+x^{16} + ... \pmod 2,$$

proving the assertion.

---

Now, please consider the generating functions $F_j$ defined to satisfy $F_{j} = x+(F_{j})^j$ with $j$ an integer greater than $1$. Define $C^{(j)}_n$ by $F_{j} = \sum_{n=0}^\infty C^{(j)}_n x^{n+1}$, with $C^{(j)}_0 = 1$.

My question is: for which $j$ does the following statement $S$ hold?

$$C^{(j)}_n \equiv 1 \pmod j \iff n = j^r - 1 \tag{S}$$

---

Here are my thoughts. First, Noam D. Elkies' answer for $j=2$ generalizes immediately for the case of $j=p$, where $p$ is prime. This is because $(a+b)^{p^m} \equiv a^{p^m} + b^{p^m} \pmod p$, which follows by induction using the key step of $(a+b)^p \equiv a^p + b^p \pmod p$. This last assertion follows from $\binom{p}{l} \equiv 0 \pmod p$ for $0<l<p$. That is, his answer generalizes to

$$F_p \equiv x+x^p+x^{p^2}+x^{p^3}+x^{p^4} + ... \pmod p,$$

which shows that indeed

$$C^{(p)}_n \equiv 1 \pmod p \iff n = p^r - 1$$

---

Numerically, I find that $\{ C^{(j)}_n \}$ also satisfies $S$ for the more general $j= p^k$, such as $j=4$, $8$, or $9$. My numerics check powers to a few thousand. Thus, I conjecture the result $$C^{(p^k)}_n \equiv 1 \pmod p^k \iff n = p^{kr} - 1$$

Note that for such $j=p^k$, the above argument means

$$F_j \equiv x+x^j+x^{j^2} + x^{j^3} + x^{j^4} +... \color{red}{\pmod p} $$

Luckily, when looking at the congruence modulo $j=p^k$ instead, there won't be any new powers of $x$ with prefactor $1$ that were missing in the congruence modulo $p$. The difficulty for me is in ruling out the possibility for prefactors of the form $mp+1$ in the congruence of $F_j$ modulo $p^k$.

---

Numerically, I find that when $j$ is not a prime nor prime power, the $\{C^{(j)}_n\}$ do not satisfy $S$. In fact, for a fixed $j\neq p^k$, there appear only to be a finite number of $\{C^{(j)}_n\}$ that are congruent to $1$ modulo $j$, and these terms are not necessarily of the requisite form of $n=j^r-1$ above. For example, for $j=6$, I find $C^{(6)}_0$,$C^{(6)}_1$, and $C^{(6)}_{66}$ are the only terms congruent to $1$ modulo $6$ up to $n=10000$. This might be evidence that the only $j$ satisfying $S$ are $j=p^k$.

---

My question follows the bolded "My question is" above, but I hope some of the above conjectures will be useful in answering my question.

---

I should note that ${C^{(j)}_n}$ takes on the values $\frac{\binom{jm}{m}}{(j-1)m+1}$ with padding by $(j-2)$ zeros in between those nonzero values, in case that offers a speedier enumeration of the $j$'s satisfying $S$.

In particular, to clarify, my question is equivalent to asking for which $j$ the following is true:

$$\frac{\binom{j n}{n}}{(j-1)n+1} \equiv 1 \pmod j \iff n = \frac{j^r -1}{j-1} \tag{S'}$$

This might put my question in contact with the method, using Lucas's theorem, in Gjergji Zaimi's answer to another question by T. Amdeberhan. To start, I think a more general version of Lucas's theorem for congruences modulo $p^k$ might be able to handle the conjecture above on the case of $j=p^k$.

Answer 1

Notice that $$\frac{1}{(j-1)n+1}\binom{j n}{n} = \frac1{jn+1}\binom{jn+1}{n}\equiv \binom{jn+1}{n}\pmod{j}.$$

Suppose that $j=p^k$ for prime $p$. Then from $\binom{jn+1}{n}\equiv 1\pmod{j}$ we can conclude that $n=\frac{j^r-1}{j-1}$ for some $r$ as follows.

Notice that if base-$p$ expansion of $n$ is $$n=d_0 + d_1 p^1 + \dots + d_m p^m,$$ then that of $jn+1$ is $$jn+1 = 1 + d_0 p^k + d_1 p^{k+1} + \dots + d_m p^{k+m}.$$ By Lucas theorem, we have with necessity $d_0\leq 1$, $d_1=d_2=\dots=d_{k-1}=0$, and $d_{k+i}\leq d_i$ for $i\geq 0$. Then, $d_i\leq d_{i-k}\leq\dots\leq d_{i\bmod k}$, and thus if $d_i>0$, then $k\mid i$ and $d_{tk}=1$ for all $t\leq \frac{i}k$. Hence, $m=(r-1)k$ and thus $n=\frac{j^r-1}{j-1}$.

Vice versa, if $n=\frac{j^r-1}{j-1}$ for some $r$, then we can use generalization of Lucas theorem given by Theorem 1 in Granville (1997) to conclude that $\binom{jn+1}{n}\equiv 1\pmod{j}$. Namely, it can be seen that in our case we have either $M_i=0$ or $R_i=0$ for all $i$, and thus in the r.h.s. of the congruence given by this theorem all terms equal to 1.

So, it remains to address the case when $j$ is not a prime power.