Abstract:

In this paper, we develop a systematic tool to calculate the congruences of some combinatorial numbers involving $n!$. Using this tool, we re-prove Kummer's and Lucas' theorems in a unique concept, and classify the congruences of the Catalan numbers $c_n$ (mod $64$). To achieve the second goal, $c_n$ (mod $8$) and $c_n$ (mod $16$) are also classified. Through the approach of these three congruence problems, we develop several general properties. For instance, a general formula with powers of $2$ and $5$ can evaluate $c_n$ (mod $2^k$) for any $k$. An equivalence $c_n\equiv_{2^k} c_{\bar{n}}$ is derived, where $\bar{n}$ is the number obtained by partially truncating some runs of $1$ and runs of $0$ in the binary string $[n]_2$. By this equivalence relation, we show that not every number in $[0,2^k-1]$ turns out to be a residue of $c_n$ (mod $2^k$) for $k\ge 2$.