\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \newcommand{\trm}{\textrm} \newcommand{\tit}{\textit} \newcommand{\mrm}{\mathrm} \newcommand{\mi}{\mathit} \newcommand{\Mobius}{M\"{o}bius} \newcommand{\blst}{\begin{trivlist}} \newcommand{\elst}{\end{trivlist}} \newcommand{\bibi}{\bibitem} \newcommand{\bslash}{\backslash} \newcommand{\HC}{\mathrm{HC}} \newcommand{\HP}{\mathrm{HP}} \newcommand{\CF}{\mathrm{CF}} \newcommand{\PF}{\mathrm{PF}} \newcommand{\D}{\mathrm{D}} \newcommand{\opp}{\oplus_{\mathrm{p}}} \newcommand{\opc}{\oplus_{\mathrm{c}}} \newcommand{\opf}{\oplus_{\mathrm{f}}} \def \nodiv{{|\kern-4.2pt/}} %%%%%%%%%%%%%%%%%%%%%% %\renewcommand{\baselinestretch}{2} %\newtheorem{thm}{Theorem} \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{conj}[thm]{Conjecture} \newtheorem{exa}[thm]{Example} \newtheorem{defn}[thm]{Definition} \newcommand{\bqu}{\begin{quotation}} \newcommand{\equ}{\end{quotation}} \newcommand{\bquu}{\begin{quote}} \newcommand{\equu}{\end{quote}} \newcommand{\bmin}[2]{\begin{minipage}[#1]{#2}} \newcommand{\emin}{\end{minipage}} \newcommand{\ben}{\begin{enumerate}} \newcommand{\een}{\end{enumerate}} \newcommand{\ble}{\begin{lem}} \newcommand{\ele}{\end{lem}} \newcommand{\bth}{\begin{thm}} \renewcommand{\eth}{\end{thm}} \newcommand{\bpr}{\begin{prop}} \newcommand{\epr}{\end{prop}} \newcommand{\bco}{\begin{cor}} \newcommand{\eco}{\end{cor}} \newcommand{\bcon}{\begin{conj}} \newcommand{\econ}{\end{conj}} \newcommand{\bde}{\begin{defn}} \newcommand{\ede}{\end{defn}} \newcommand{\bex}{\begin{exa}} \newcommand{\eex}{\end{exa}} \newcommand{\barr}{\begin{array}} \newcommand{\earr}{\end{array}} \newcommand{\btab}{\begin{tabular}} \newcommand{\etab}{\end{tabular}} \newcommand{\beq}{\begin{equation}} \newcommand{\eeq}{\end{equation}} \newcommand{\beqq}{$$} \newcommand{\eeqq}{$$} \newcommand{\bea}{\begin{eqnarray*}} \newcommand{\eea}{\end{eqnarray*}} \newcommand{\beaa}{\begin{eqnarray}} \newcommand{\eeaa}{\end{eqnarray}} \newcommand{\bce}{\begin{center}} \newcommand{\ece}{\end{center}} \newcommand{\bpi}{\begin{picture}} \newcommand{\epi}{\end{picture}} \newcommand{\bfi}{\begin{figure}\begin{center}} \newcommand{\efi}{\end{center}\end{figure}} \newcommand{\capt}{\caption} \newcommand{\bsl}{\begin{slide}{}} \newcommand{\esl}{\end{slide}} \newcommand{\ch}{\choose} \newcommand{\bib}{thebibliography} \newcommand{\pf}{{\bf Proof.}\quad} %\newcommand{\qed}{\rule{1ex}{1ex}} \newcommand{\Qed}{\hfill{\rule{1ex}{1ex} \medskip}} \newcommand{\mc}[2]{\multicolumn{#1}{#2}} \newcommand{\ul}{\underline} \newcommand{\ol}{\overline} \newcommand{\hs}[1]{\hspace{#1}} \newcommand{\vs}[1]{\vspace{#1}} \newcommand{\ssk}{\smallskip} \newcommand{\msk}{\mediumskip} \newcommand{\bsk}{\bigskip} \newcommand{\rp}[2]{\rule{#1pt}{#2pt}} \newcommand{\st}[1]{\rule{#1}{0pt}} \newcommand{\mbl}[1]{\makebox(0,0)[l]{#1}} \newcommand{\mbr}[1]{\makebox(0,0)[r]{#1}} \newcommand{\mbt}[1]{\makebox(0,0)[t]{#1}} \newcommand{\mbb}[1]{\makebox(0,0)[b]{#1}} \newcommand{\mbc}[1]{\makebox(0,0){#1}} \newcommand{\emp}{\emptyset} \newcommand{\sbs}{\subset} \newcommand{\sbe}{\subseteq} \newcommand{\sps}{\supset} \newcommand{\spe}{\supseteq} \newcommand{\setm}{\setminus} \newcommand{\asy}{\thicksim} \newcommand{\dle}{<\hspace{-6pt}\cdot} \newcommand{\dge}{\cdot\hspace{-6pt}>} \newcommand{\iso}{\cong} \newcommand{\con}{\equiv} \newcommand{\mh}{\hat{0}} \newcommand{\Mh}{\hat{1}} \newcommand{\Dh}{\hat{D}} \newcommand{\zh}{\hat{0}} \newcommand{\oh}{\hat{1}} \newcommand{\Ph}{\hat{P}} \newcommand{\Pih}{\hat{\Pi}} \newcommand{\Sh}{\hat{S}} \newcommand{\lh}{\hat{l}} \newcommand{\xh}{\hat{x}} \newcommand{\ptn}{\vdash} \newcommand{\lt}{\lhd} \newcommand{\gt}{\rhd} \newcommand{\lte}{\unlhd} \newcommand{\gte}{\unrhd} \newcommand{\jn}{\vee} \newcommand{\Jn}{\bigvee} \newcommand{\mt}{\wedge} \newcommand{\Mt}{\bigwedge} \newcommand{\bdy}{\partial} \newcommand{\sd}{\bigtriangleup} \newcommand{\case}[4]{\left\{\barr{ll}#1&\mbox{#2}\\#3&\mbox{#4}\earr\right.} \newcommand{\fl}[1]{\lfloor #1 \rfloor} \newcommand{\ce}[1]{\lceil #1 \rceil} \newcommand{\flf}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor} \newcommand{\cef}[2]{\left\lceil\frac{#1}{#2}\right\rceil} \newcommand{\gau}[2]{\left[ #1 \atop #2 \right]} \newcommand{\setc}[2]{\{left{#1}\ :\ #2\}} \newcommand{\setl}[2]{\{left{#1}\ |\ #2\}} \newcommand{\qst}{$q$-Stirling numbers} \newcommand{\qbi}{$q$-binomial coefficients} \newcommand{\del}{\nabla} \newcommand{\pde}[2]{\frac{\partial#1}{\partial#2}} \newcommand{\spd}[2]{\frac{\partial^2\hspace{-2pt}#1}{\partial#2^2}} \newcommand{\ode}[2]{\ds\frac{d#1}{d#2}} \newcommand{\fal}[1]{\langle{#1}\rangle} \newcommand{\fall}[2]{\langle{#1}\rangle_{#2}} \newcommand{\nor}[1]{\parallel{#1}\parallel} \newcommand{\ipr}[1]{\langle{#1}\rangle} \newcommand{\lb}{\left\{} \newcommand{\rb}{\right\}} \newcommand{\ree}[1]{(\ref{#1})} \newcommand{\rpl}{$\longleftarrow$} \newcommand{\ra}{\rightarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\rla}{\leftrightarrow} \newcommand{\Rla}{\Leftrightarrow} \newcommand{\lra}{\longrightarrow} \newcommand{\Lra}{\Longrightarrow} \newcommand{\llra}{\longleftrightarrow} \newcommand{\Llra}{\Longleftrightarrow} \newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\ga}{\gamma} \newcommand{\de}{\delta} \newcommand{\ep}{\epsilon} \newcommand{\io}{\iota} \newcommand{\ka}{\kappa} \newcommand{\la}{\lambda} \newcommand{\mut}{\tilde{\mu}} \newcommand{\om}{\omega} \newcommand{\si}{\sigma} \renewcommand{\th}{\theta} \newcommand{\ze}{\zeta} \newcommand{\Al}{\Alpha} \newcommand{\Ga}{\Gamma} \newcommand{\De}{\Delta} \newcommand{\Ep}{\epsilon} \newcommand{\Vep}{varepsilon} \newcommand{\La}{\Lambda} \newcommand{\Om}{\Omega} \newcommand{\Si}{\Sigma} \newcommand{\Th}{\Theta} \newcommand{\Ze}{\Zeta} \newcommand{\ba}{{\bf a}} \newcommand{\bb}{{\bf b}} \newcommand{\bc}{{\bf c}} \newcommand{\bd}{{\bf d}} \newcommand{\bi}{{\bf i}} \newcommand{\bj}{{\bf j}} \newcommand{\bk}{{\bf k}} \newcommand{\bm}{{\bf m}} \newcommand{\bn}{{\bf n}} \newcommand{\bp}{{\bf p}} \newcommand{\bq}{{\bf q}} \newcommand{\br}{{\bf r}} \newcommand{\bs}{{\bf s}} \newcommand{\bt}{{\bf t}} \newcommand{\bu}{{\bf u}} \newcommand{\bv}{{\bf v}} \newcommand{\bw}{{\bf w}} \newcommand{\bx}{{\bf x}} \newcommand{\by}{{\bf y}} \newcommand{\bA}{{\bf A}} \newcommand{\bB}{{\bf B}} \newcommand{\bC}{{\bf C}} \newcommand{\bE}{{\bf E}} \newcommand{\bF}{{\bf F}} \newcommand{\bN}{{\bf N}} \newcommand{\bP}{{\bf P}} \newcommand{\bQ}{{\bf Q}} \newcommand{\bR}{{\bf R}} \newcommand{\bT}{{\bf T}} \newcommand{\bX}{{\bf X}} \newcommand{\bXh}{\hat{{\bf X}}} \newcommand{\bZ}{{\bf Z}} \newcommand{\bbC}{{\mathbb C}} \newcommand{\bbF}{{\mathbb F}} \newcommand{\bbN}{{\mathbb N}} \newcommand{\bbP}{{\mathbb P}} \newcommand{\bbR}{{\mathbb R}} \newcommand{\bbZ}{{\mathbb Z}} \newcommand{\cA}{{\cal A}} \newcommand{\cB}{{\cal B}} \newcommand{\cC}{{\cal C}} \newcommand{\cD}{{\cal D}} \newcommand{\cE}{{\cal E}} \newcommand{\cF}{{\cal F}} \newcommand{\cG}{{\cal G}} \newcommand{\cH}{{\cal H}} \newcommand{\cI}{{\cal I}} \newcommand{\cIF}{{\cal IF}} \newcommand{\cJ}{{\cal J}} \newcommand{\cK}{{\cal K}} \newcommand{\cL}{{\cal L}} \newcommand{\cM}{{\cal M}} \newcommand{\cME}{{\cal ME}} \newcommand{\cO}{{\cal O}} \newcommand{\cP}{{\cal P}} \newcommand{\cQ}{{\cal Q}} \newcommand{\cR}{{\cal R}} \newcommand{\cRF}{{\cal RF}} \newcommand{\cS}{{\cal S}} \newcommand{\cT}{{\cal T}} \newcommand{\cW}{{\cal W}} \newcommand{\cAB}{{\cal AB}} \newcommand{\cBC}{{\cal BC}} \newcommand{\cDB}{{\cal DB}} \newcommand{\cAD}{{\cal AD}} \newcommand{\cNBC}{{\cal NBC}} \newcommand{\df}{\dot{f}} \newcommand{\dF}{\dot{F}} \newcommand{\fS}{{\mathfrak S}} \newcommand{\at}{\tilde{a}} \newcommand{\ct}{\tilde{c}} \newcommand{\dt}{\tilde{d}} \newcommand{\Bt}{\tilde{B}} \newcommand{\Gt}{\tilde{G}} \newcommand{\Ht}{\tilde{H}} \newcommand{\Kt}{\tilde{K}} \newcommand{\Nt}{\tilde{N}} \newcommand{\St}{\tilde{S}} \newcommand{\alt}{\tilde{\alpha}} \newcommand{\bet}{\tilde{\beta}} \newcommand{\rht}{\tilde{\rho}} \newcommand{\Pit}{\tilde{\Pi}} \newcommand{\tal}{\tilde{\alpha}} \newcommand{\tbe}{\tilde{\beta}} \newcommand{\tPi}{\tilde{\Pi}} \newcommand{\ab}{\ol{a}} \newcommand{\Bb}{\ol{B}} \newcommand{\cb}{\ol{c}} \newcommand{\Cb}{\ol{C}} \newcommand{\db}{\ol{d}} \newcommand{\Db}{\ol{D}} \newcommand{\eb}{\ol{e}} \newcommand{\Eb}{\ol{E}} \newcommand{\fb}{\ol{f}} \newcommand{\Gb}{\ol{G}} \newcommand{\Hb}{\ol{H}} \newcommand{\kb}{\ol{k}} \newcommand{\Kb}{\ol{K}} \newcommand{\nb}{\ol{n}} \newcommand{\pb}{\ol{p}} \newcommand{\Phib}{\ol{\Phi}} \newcommand{\Qb}{\ol{Q}} %\newcommand{\Sb}{\ol{S}} \newcommand{\Wb}{\ol{W}} \newcommand{\xb}{\ol{x}} \newcommand{\yb}{\ol{y}} \newcommand{\Yb}{\ol{Y}} \newcommand{\zb}{\ol{z}} \newcommand{\pib}{\ol{\pi}} \newcommand{\sib}{\ol{\si}} \newcommand{\degb}{\ol{\deg}} \newcommand{\vj}{\vec{\jmath}} \newcommand{\mrp}{\mathrm{p}} \newcommand{\mrq}{\mathrm{q}} \newcommand{\mrr}{\mathrm{r}} \newcommand{\mrs}{\mathrm{s}} \newcommand{\mrt}{\mathrm{t}} \newcommand{\mru}{\mathrm{u}} \newcommand{\mrv}{\mathrm{v}} \newcommand{\mrw}{\mathrm{w}} \newcommand{\mrx}{\mathrm{x}} \newcommand{\mry}{\mathrm{y}} \newcommand{\Aut}{\mathop{\rm Aut}} \newcommand{\abl}{\mathop {\rm al}} \newcommand{\capa}{\mathop{\rm cap}} \newcommand{\codim}{\mathop{\rm codim}} \newcommand{\col}{\mathop{\rm col}} \newcommand{\Der}{\mathop{\rm Der}} \newcommand{\des}{\mathop{\rm des}} \newcommand{\Des}{\mathop{\rm Des}} \newcommand{\diag}{\mathop{\rm diag}} \newcommand{\diam}{\mathop{\rm diam}} \newcommand{\ev}{\mathop{\rm ev}} \newcommand{\eval}{\mathop{\rm eval}} \newcommand{\Eval}{\mathop{\rm Eval}} \newcommand{\FPF}{\mathop{\rm FPF}} \newcommand{\Harm}{{\rm Harm}} \newcommand{\Hom}{{\rm Hom}} \newcommand{\id}{\mathop {\rm id}} \newcommand{\inc}{\mathop {\rm inc}} \newcommand{\Ind}{\mathop {\rm Ind}} \newcommand{\inter}{\mathop {\rm int}} \newcommand{\Inter}{\mathop {\rm Int}} \newcommand{\inv}{\mathop {\rm inv}} \newcommand{\Inv}{\mathop {\rm Inv}} \newcommand{\lcm}{\mathop {\rm lcm}} \newcommand{\LHS}{\mathop {\rm LHS}} \newcommand{\Mat}{\mathop {\rm Mat}} \newcommand{\maj}{\mathop {\rm maj}} \newcommand{\Mod}{\mathop{\rm mod}} \newcommand{\nin}{\mathop {\rm nin}} \newcommand{\Nin}{\mathop {\rm Nin}} \newcommand{\nul}{\mathop {\rm nul}} \newcommand{\od}{\mathop {\rm od}} \newcommand{\per}{\mathop {\rm per}} \newcommand{\pfa}{\mathop {\rm pf}} \newcommand{\Pm}{\mathop {\rm pm}} \newcommand{\PM}{\mathop {\rm PM}} \newcommand{\Pol}{{\rm Pol}} \newcommand{\rad}{\mathop {\rm rad}} \newcommand{\RHS}{\mathop {\rm RHS}} \newcommand{\rk}{\mathop{\rm rk}} \newcommand{\rank}{\mathop{\rm rank}} \newcommand{\row}{\mathop{\rm row}} \newcommand{\sdiam}{\mathop{\rm sdiam}} \newcommand{\sgn}{\mathop{\rm sgn}} \newcommand{\slack}{{\rm slack}} \newcommand{\summ}{\mathop{\rm sum}} \newcommand{\tang}{\mathop{\rm tang}} \newcommand{\tr}{\mathop{\rm tr}} \newcommand{\wt}{\mathop {\rm wt}} \newcommand{\wed}{\mathop {\rm wedge}} \newcommand{\sus}{\mathop {\rm susp}} \newcommand{\Sym}{\mathop {\rm Sym}} \newcommand{\dil}{\displaystyle} \newcommand{\scl}{\scriptstyle} \newcommand{\ssl}{\scriptscriptstyle} \newcommand{\foz}{\footnotesize} \newcommand{\scz}{\scriptsize} \newcommand{\cho}{\choose} \newcommand{\Schu}{Sch\"utzenberger}{} \newcommand{\aim}{Adv.\ in Math.}{} \newcommand{\alu}{Alg.\ Univ.}{} \newcommand{\bams}{Bull.\ Amer.\ Math.\ Soc.}{} \newcommand{\cjm}{Canad.\ J.\ Math.}{} \newcommand{\dm}{Discrete Math.}{} \newcommand{\dmj}{Duke Math.\ J.}{} \newcommand{\ejc}{European J.\ Combin.}{} \newcommand{\im}{Invent.\ Math.}{} \newcommand{\jaa}{J.\ Algebra}{} \newcommand{\jac}{J.\ Algebraic Combin.}{} \newcommand{\jas}{J.\ Algorithms}{} \newcommand{\jams}{J.\ Amer.\ Math.\ Soc.}{} \newcommand{\jct}{J.\ Combin.\ Theory}{} \newcommand{\jcta}{J.\ Combin.\ Theory Ser.\ A}{} \newcommand{\jctb}{J.\ Combin.\ Theory Ser.\ B}{} \newcommand{\jgt}{J.\ Graph Theory}{} \newcommand{\jram}{J.\ Reine Angew. Math.}{} \newcommand{\pjm}{Pacific J.\ Math.}{} \newcommand{\pams}{Proc.\ Amer.\ Math.\ Soc.}{} \newcommand{\plms}{Proc.\ London Math.\ Soc.}{} \newcommand{\tams}{Trans.\ Amer.\ Math.\ Soc.}{} \newcommand{\pja}{Proc.\ Japan Acad.\ Ser.\ A Math}{} \newcommand{\sv}{Springer-Verlag Lecture Notes in Math.}{} \newcommand{\ds}{\displaystyle}{} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Catalan Numbers Modulo $2^k$ } \vskip 1cm \large Shu-Chung Liu\footnote{Partially supported by NSC96-2115-M-134-003-MY2}\\ Department of Applied Mathematics\\ National Hsinchu University of Education \\ Hsinchu, Taiwan \\ \href{liularry@mail.nhcue.edu.tw}{\tt liularry@mail.nhcue.edu.tw} \\ \ \\ and \\ \ \\ Jean C.-C. Yeh\\ Department of Mathematics\\ Texas A \& M University\\ College Station, TX 77843-3368\\ USA\\ \end{center} \vskip .2 in \begin{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$. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Remark} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} %%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%% \section{Introduction} Throughout this paper, $p$ is a prime number and $k$ is a positive integer. We are interested in enumerating the congruences of various combinatorial numbers modulo a prime power $q:=p^k$, and one of the goals of this paper is to classify Catalan numbers $c_n$ modulo $64$. For a prime modulus $p$, previous studies can be traced back to the famous Pascal's fractal formed by the parities of binomial coefficients $\binom{n}{k}$~(see for example~\cite{Wolfram_02}). As a pioneer in this problem, Kummer formulated the maximum power of $p$ dividing $\binom{n}{k}$~\cite[see also Theorem~\ref{t_kummer_852}]{Kummer_852}. Lucas, another early researcher, developed the very useful calculating formula $\binom{n}{k}\equiv_p \prod_i \binom{n_i}{r_i}$, where ``$\equiv_p$'' denotes the equivalence of congruence modulo $p$; and each $n_i$ (similarly for each $r_i$) is obtained from $[n]_p :=\langle n_s\cdots n_1n_0\rangle_p$ denoting the sequence of digits representing $n$ in the base-$p$ system~\cite[or see Theorem~\ref{t_Lucas_877}]{Lucas_877}. A generalization of Lucas' Theorem for a prime power was established by Davis and Webb~\cite{Davis_Webb_90}. The classical problem of Pascal's triangle also has versions for modulus $4$ and modulus $8$~\cite{Davis_Webb_91, Huard_Spearman_Williams_98}. The behavior of Pascal's triangle modulo higher powers of $p$ is more complicated. Some rules of the behavior are discussed by Granville~\cite{Granville_92}. The reader can also refer to~\cite{Granville} for a survey of binomial coefficients modulo prime powers. Several other combinatorial numbers have been studied for their congruences, for example, Ap\'{e}ry numbers~\cite{Gessel_82, Mimura_83}, Central Delannoy numbers~\cite{Eu_Liu_Yeh_06} and weighted Catalan numbers~\cite{Rost_Sagan_94}. The \emph{$p$-adic order} of a positive integer $n$ is denoted and defined as $$ \omega_p(n):=\max\{\alpha\in\bbN : p^{\alpha}|n\}. $$ We also use $p^\alpha\|n$ to denote the property that $p^\alpha |n$ but $p^{\alpha+1} \nodiv n$. The \emph{cofactor of $n$ with respect to $p^{\omega_p(n)}$}, which is denoted and defined as $$CF_p(n):=\frac{n}{p^{\omega_p(n)}},$$ is an important object in this paper. We also call $CF_p(n)$ the (\emph{maximal}) \emph{$p$-free factor} of $n$. The value $\omega_p$ indicates the divisibility by powers of $p$, which can be found in many previous studies (see for example~\cite{Dickson_19}). However, the studies on $CF_p$ was a little bit rare before. One of formulae about $CF_p$ is that \beq \label{e_CFpBin} CF_p({m\choose n})\equiv_p (-1)^{\omega_p({m\choose n})} \prod_{i\ge 0}\frac{m_i!}{n_i!r_i!}, \eeq where $r=m-n$. This formula was found by each of Anton (1869), Stickelberger (1890) and Hensel (1902). A generalized formula of \ree{e_CFpBin} for modulus $p^k$ can be found in~\cite{Granville}. Recently, Eu, Liu and Yeh used $CF_p$ to enumerate the congruences of Catalan numbers and Motzkin number modulo $4$ and $8$~\cite{Eu_Liu_Yeh_07}. Note that this cofactor was denoted by $NF_p(n)$ in their paper. Given a product $\prod_{i=1}^a M_i$ of integers $M_i$, clearly $\omega_p(\prod_{i=1}^a M_i)= \sum_{i=1}^a \omega_p(M_i)$ and usually it is easy to calculate; but $CF_p(\prod_{i=1}^a M_i)$ (mod $q$) is more difficult to evaluate. However, $q$ and $CF_p(M_i)$ are coprime; so instead of considering the arithmetics in the ring $\bbZ_q:= \bbZ /q\bbZ$, we shall narrow our attention to the \emph{modulo multiplication group} $\bbZ^\ast_q:=\{t\in \bbZ_q\mid (t,q)=1\}$. To evaluate $CF_p$ (mod $q$), Eu, Liu and Yeh~\cite{Eu_Liu_Yeh_07} recently introduced a new index $E_{q,t}$, the \emph{$t$-encounter function of modulus $q$}, with respect to a product $\prod_{i=1}^a M_i$ is denoted and defined as $$ E_{q,t}(\prod_{i=1}^a M_i):=\sum_{i=1}^a \chi( CF_p(M_i)\equiv_q t), $$ where $\chi$ is the Boolean function. If $\omega_p(\prod_{i=1}^a M_i)\ge k$, then $\prod_{i=1}^a M_i \equiv_q 0$; otherwise \beq \label{e_omega_Eq} \prod_{i=1}^a M_i \equiv_q p^{\omega_p(\prod_{i=1}^a M_i)} \prod_{t\in \bbZ_q^\ast} t^{\,E_{q,t}(\prod_{i=1}^a M_i)}. \eeq The evaluation of $\prod_{t\in \bbZ_q^\ast} t^{\,E_{q,t}(\prod_{i=1}^a M_i)}$ shall be operated in $\bbZ^\ast_q$. Alternatively and more efficiently, \beq \label{e_omega_Eq2} \prod_{i=1}^a M_i \equiv_q p^{\omega_p(\prod_{i=1}^a M_i)} \prod_{t\in \bbZ_{q'}^\ast} t^{\,E_{q',t}(\prod_{i=1}^a M_i)}, \eeq where $q'=p^{k'}$ with some $k'$ such that $k-\omega_p(\prod_{i=1}^a M_i)\le k'\le k$. Many combinatorial numbers are in form of quotient $\prod_{i=1}^a M_i/\prod_{j=1}^b N_j$. By analogy, let us define $$ E_{q,t}(\frac{\prod_{i=1}^a M_i}{\prod_{j=1}^b N_j}):= E_{q,t}(\prod_{i=1}^a M_i)-E_{q,t}( \prod_{j=1}^b N_j), $$ and then \beq \label{e_omega_Eq3} \frac{\prod_{i=1}^a M_i}{\prod_{j=1}^b N_j} \equiv_q p^{\om_p(\prod_{i=1}^a M_i)-\om_p(\prod_{j=1}^b N_j)} \prod_{t\in \bbZ_q^\ast} t^{\,E_{q,t}(\frac{\prod_{i=1}^a M_i}{\prod_{j=1}^b N_j})}. \eeq In this paper, we first investigate the most primitive product, namely the factorial $n!$, and then study the Catalan number $c_n:=\frac{(2n)!}{(n+1)(n!)^2}$. By enumerating $\omega_2$ and $E_{q,t}$ for $q=4$ and $8$, Eu, Liu and Yeh characterized the congruences of Catalan numbers and Motzkin numbers modulo $4$ and $8$~\cite{Eu_Liu_Yeh_07}. Here we improve their calculating techniques and challenge higher moduli up to $64$. It is well known that $\bbZ_{2^k}^\ast$ is isomorphic to $C_2\times C_{2^{k-2}}$ ($k\ge 2$), and the group $\bbZ_{p^k}^\ast$ is cyclic for any odd prime $p$. A breakthrough of our work is that by transforming the multiplicative group $\bbZ_n^\ast$ to the corresponding additive group and fitting $\prod_{t\in \bbZ_q^\ast} t^{\,E_{q,t}(\prod_{i=1}^a M_i)}$ into an admissible additive process, we can develop efficient and powerful formulae for enumerating the congruences of many combinatorial numbers. With this new tool, the time-consuming methods in~\cite{Eu_Liu_Yeh_07} become easy applications. We not only work for moduli $8$, $16$ and $64$, but also develop several general properties. In Theorem~\ref{t_cn_mod_q_1}, we derive that $c_n$ (mod $2^k$) is equivalent to the multiple of certain powers of $2$ and $5$. In Corollaries~\ref{c_Cat_2_k-1}, \ref{c_cn_eq} and \ref{c_cn_eq16}, we derive three easy formulae for $c_n$ (mod $2^k$) in case that $\omega_2(c_n)=k-d$ for $d=1,2,3$ respectively. In addition, Theorems~\ref{t_n_tn} and~\ref{t_cn_bar_n} provide two rough classifications for $CF_2(n!)$ and $c_n$ (mod $2^k$) respectively. The second classification offers a shortcut to enumerate $c_n$ (mod $2^k$) when $n$ is very large. It also implies Theorem~\ref{t_con_cn_upb}, which claims that not every number in $[0,2^k-1]$ admits to be a congruence of $c_n$ (mod $2^k$) for $k\ge 2$. The paper is organized as follows. In Section~\ref{s_oE_BC}, the tools $CF_{2}$ and $E_{2^k,t}$, introduced by Eu, Liu and Yeh~\cite{Eu_Liu_Yeh_07}, are generalized to work for any prime $p$, and then we re-prove Kummer's and Lucas' Theorems using a unique idea---the concept of $\omega_p$ and $E_{q,t}$. An isomorphism $T_q$ from the multiplicative group $\bbZ_{p^k}^\ast$ to an additive group is introduced in Section~\ref{s_Zqast_C}. Some results for $T_{2^k}(CF_2(n!))$ and $T_{2^k}(CF_2(c_n))$ are given there. In Sections~\ref{s_bu8_cm8}, \ref{s_u16_cm16} and \ref{s_u32_u64_cm64}, we study the congruences of $c_n$ with moduli $8$ (re-proving the result in ~\cite{Eu_Liu_Yeh_07}), $16$ and $64$, respectively. Several comments for further research are given in Section~\ref{s_FR_A}, the final section. \section{$\omega_p(n!)$ and $E_{q,t}(n!)$; Borrows and Carries} \label{s_oE_BC} Recall the $p$-adic order $\omega_p$ and $t$-encounter function $E_{q,t}$ defined in the previous section. Since the factorial $n!$ is the most elementary piece in the formulae of various combinatorial numbers, it is crucial to investigate $\omega_p(n!)$ and $E_{q,t}(n!)$. The first lemma of this section is generalized from the two similar lemmas in \cite{Eu_Liu_Yeh_07}. Before giving that lemma, we need some new notation. Let $[a,b]:=\{a,a+1,\ldots, b\}$ for two integers $a$ and $b$, where $a\le b$. Additionally, let $[a,b]_{\text{o}}$ contain all odd numbers in $[a,b]$. Given a positive integer $n$, which is normally represented by a decimal expansion using Arabic numerals $0,1,\ldots,9$, we want to transform it into a base-$p$ expansion using \emph{digits} $0,1,\ldots,p-1$. Such an expansion is denoted as a sequence of digits $$ [n]_p:= \langle n_rn_{r-1}\cdots n_1n_0 \rangle_p, $$ provided $p^r\le n < p^{r+1}$ for some $r\in \bbN$ and $n=n_r p^r+n_{r-1}p^{r-1}+\dots + n_1p+n_0$ with $n_i\in [0, p-1]$, where $n_i$ is called the \emph{$i$-th place digit} of $[n]_p$ (or of $n$). For convenience, we also let $n_{r+1}= n_{r+2}= \cdots= 0$, but formally these $0$'s of higher places do not belong to the sequence $[n]_p$. We can even define $[0]_p$ as an empty sequence. Reversely, we define $$ |\langle n_rn_{r-1}\cdots n_1n_0 \rangle_p|:= n_r p^r+n_{r-1}p^{r-1}+\dots + n_1p+n_0=n. $$ Let $d_s(n):=\sum_{i\ge s} n_i$ which is the \emph{digit sum} starting from the $s$-th place. We simply let $d(n)=d_0(n)$, called the \emph{total digit sum}. \ble \label{l_power_p} Let $q=p^k$, $t\in\bbZ_q^\ast$ and $[n]_p=\langle n_rn_{r-1}\dots n_1n_0\rangle_p$. The $p$-adic order $\omega_p(n!)$ and $t$-encounter function $E_{q,t}(n!)$ are evaluated as follows: \beaa \omega_p(n!) &=& \frac{n-d(n)}{p-1}, \label{e_om_nfac}\\ E_{q,t}(n!) &=& \frac{|\langle n_r\cdots n_k n_{k-1}\rangle_p| -d_{k-1}(n)}{p-1} + \sum_{i\ge 0}\chi(|\langle n_{i+k-1}\cdots n_{i+1}n_i\rangle_p| \ge t). \label{e_encounter} \eeaa \ele \pf We have \bea \omega_p(n!) &=& \sum_{k=1}^s \lfloor n/p^k\rfloor \\ &=& |\langle n_rn_{r-1}\dots n_2n_1 \rangle_p|+|\langle n_rn_{r-1}\dots n_2\rangle_p|+\dots +|\langle n_r\rangle_p|, \eea because $\lfloor n/p^k\rfloor$ counts the number of integers in $[1,n]$ that are multiples of $p^k$. From this equation, the total contribution to $\omega_p(n!)$ caused by $n_k$ is $(p^{k-1}+p^{k-2}+ \cdots + 1) n_k$. Thus, $\omega_p(n!)= \sum_{k=1}^{s}\frac{(p^k-1)}{p-1}n_k = \sum_{k=0}^{s}\frac{(p^k-1)}{p-1}n_k= \frac{n-d(n)}{p-1}$ and the proof of the first equation follows. The concept for the proof of the second equation is similar. For those $m\in [1,n]$ with the same order $\omega_p(m)=i$, the sum of their $\chi (m/p^{i}\equiv_q t)$ equals $\left\lfloor ({\lfloor \frac{n}{p^i}\rfloor+(q-t)})/{q}\right\rfloor$. We add $q-t$ into the numerator because the terms occurring of congruence $t$ are, from $1$ to $n$, the $t$-th, $(t+q)$-th, $(t+2q)$-th, etc. Therefore, we have \beaa E_{q,t}(n!) &=& \sum_{i\ge 0}\left\lfloor \frac{\lfloor \frac{n}{p^i} \rfloor+(q-t)}{q}\right\rfloor \label{e_E4} \\ &=& \sum_{i\ge k-1} \frac{(p^{i-k+1}-1)n_i}{p-1}+\sum_{i\ge 0} \chi(|\langle n_{i+k-1}\cdots n_{i+1}n_i\rangle_p| \ge t) \label{e_two_terms}\\ &=& \frac{|\langle n_r\cdots n_k n_{k-1}\rangle_p| -d_{k-1}(n)}{p-1} + \sum_{i\ge 0}\chi(|\langle n_{i+k-1}\cdots n_{i+1}n_i\rangle_p| \ge t), \nonumber \eeaa where the second summation in (\ref{e_two_terms}) counts the effect of the floor function caused by $q-t$ in (\ref{e_E4}), while the first summation is obtained by ignoring $q-t$. \Qed Note that equation \ree{e_om_nfac} is the Legendre formula. For convenience, we shall evaluate the two terms in~\ree{e_encounter} separately. Let $E_{q,t}(n!):=E'_q(n!) +E''_{q,t}(n!)$ by defining \beaa E'_q(n!) &:=& \frac{|\langle n_r\cdots n_{k-1}\rangle_p|-d_{k-1}(n)}{p-1}, \text{ and} \label{e_E_prime}\\ E''_{q,t}(n!)&:=& \sum_{i\ge 0} \chi(|\langle n_{i+k-1}\cdots n_{i+1}n_i\rangle_p|\ge t). \label{e_E_2prime} \eeaa Also note that the digit $n_{k-1}$ actually does not affect the value of $E'_q(n!)$. It is the same as for $n_{0}$ to $\omega_p(n!)$. The products $(m+n)!$ and $(m-n)!$ also occur frequently in the formulae of various combinatorial numbers. To apply Lemmas~\ref{l_power_p} directly, we have to realize every digit in $[m+n]_p$ and $[m-n]_p$. Can we simply rely on the digits in $[m]_p$ and $[n]_p$ without operating summation $m+n$ and subtraction $m-n$ completely? We fulfill this idea in the following. Given nonnegative integers $m\ge n$ and $i\ge j$, let us define \bea \beta^+_p(m,n;i,j)&:=& \chi(|\fal{m_im_{i-1}\cdots m_j}_p| + |\fal{n_in_{i-1}\cdots n_j}_p| \ge p^{i-j+1}),\\ \beta^-_p(m,n;i,j)&:=& \chi(|\fal{m_im_{i-1}\cdots m_j}_p| < |\fal{n_in_{i-1}\cdots n_j}_p|), \eea and briefly let $\beta^+_p(m,n;i):=\beta^+_p(m,n;i,0)$ and $\beta^-_p(m,n;i):=\beta^-_p(m,n;i,0)$, which indicate respectively the possible \emph{carry} and \emph{borrow} transmitting between the $i$-th and the $(i+1)$-st places when we operate summation $m+n$ and subtraction $m-n$ in the base-$p$ system. Define \bea C_p(m,n) &:=& \sum_{i\ge 0} \beta^+_p(m,n;i) \text{ and}\\ B_p(m,n) &:=& \sum_{i\ge 0} \beta^-_p(m,n;i), \eea which are respectively the numbers of \emph{total carries} for (operating) $m+n$ and \emph{total borrows} for $m-n$. \ble \label{l_dig_sun_n_r} Let $m,n,i\in \bbN$ with $m\ge n$. In the base-$p$ system, we have \bea d(m+n) &=& d(m)+d(n)- (p-1) C_p(m,n) \text{ and}\\ d(m-n) &=& d(m)-d(n)+ (p-1) B_p(m,n). \eea \ele \pf Let us observe the ``net contribution'' to $d(m+n)$ made by the two $i$-th place digits in $[m]_p$ and $[n]_p$, when operating $m+n$ in the base-$p$ system. We claim that this net contribution is $$ m_i+n_i-\beta^+_p(m,n;i)(p-1). $$ The first equation of the lemma directly follows this claim. If no carry occurs at the $i$-th place, then $(m+n)_i= m_i+n_i+\beta^+_p(m,n;i-1)$. So $(m+n)_i$ (as well as the digit sum $d(m+n)$) simply obtains net contribution $m_i+n_i$ from these two digits. Note that $\beta^+_p(m,n;i-1)$ may increase $(m+n)_i$; however, as for ``net contribution'' it has been counted at the $(i-1)$-st place. If a carry occurs, both $(m+n)_i$ and $(m+n)_{i+1}$ are effected, while $(m+n)_i$ turns to be $m_i+n_i+ \beta^+_p(m,n;i-1)-p$ and $(m+n)_{i+1}$ obtains an extra $1=\beta^+_p(m,n;i)$. Thus, the net contribution to $d(m+n)$ causing by $m_i$ and $n_i$ is then $m_i+n_i-p+1$. So the claim follows. By a similar way, we can explain why $(p-1)B_p(m,n)$ must be added into the second equation. \Qed Now applying Lemmas~\ref{l_power_p} and~\ref{l_dig_sun_n_r}, we obtain the following result. \ble \label{l_power_n-r} Let $n\ge n$ and suppose $[m]_p=\fall{\dots m_1m_0}{p}$ and $[n]_p=\fall{\dots n_1n_0}{p}$. Than \bea \omega_p((m+n)!)&=& \frac{m+n-d(m)-d(n)}{p-1}+ C_p(m,n) \text{ and} \\ \omega_p((m-n)!)&=& \frac{m-n-d(m)+d(n)}{p-1}- B_p(m,n). \eea \ele Both $E_{q,t}((m+n)!)$ and $E_{q,t}((m-n)!)$ are useful, but not in this paper; so we skip them here. Before ending this section, we use $\omega_p$ and $E_{q,t}$ to re-prove the following two famous and useful theorems. \bth[Kummer, 1852~\cite{Kummer_852}] \label{t_kummer_852} Let $p$ be a prime and $m,n\in \bbN$ with $m\ge n$. Then we have \bea \omega_p(\binom{m+n}{m}) &=& C_p(m,n) \text{ and}\\ \omega_p(\binom{m}{n}) &=& B_p(m,n). \eea \eth \pf By Lemmas~\ref{l_power_p} and~\ref{l_power_n-r}, we derive \bea \omega_p(\binom{m+n}{m}) &=& \omega_p((m+n)!) - \omega_p(m!) - \omega_p(n!)\\ &=& \left[\frac{m+n-d(m)-d(n)}{p-1}+ C_p(m,n)\right] -\frac{m-d(m)}{p-1} -\frac{n-d(n)}{p-1}\\ &=& C_p(m,n). \eea The proof for $\omega_p(\binom{m}{n})$ is similar. \Qed \bth[Lucas, 1877~\cite{Lucas_877}] \label{t_Lucas_877} The binomial coefficient modulo a prime $p$ can be computed as follows $$ \binom{m}{n}\equiv_p \prod_{i\ge 0}\binom{m_i}{n_i}, $$ where $\fall{\cdots m_1m_0}{p}$ and $\fall{\cdots n_1n_0}{p}$ are the expansions of $m$ and $n$ in the base-$p$ system, respectively. \eth \pf We may assume that $m_i\ge n_i$ for all $i$. Because $m_i< n_i$ means that a borrow occurs and then $p|\binom{m}{n}$ by Kummer's Theorem. Also $\binom{m_i}{n_i}=0$ is due to $m_i< n_i$. So the stated equivalence holds. By assumption, we have $\omega_p(\binom{m}{n})=0$ and $(m-n)_i=m_i-n_i$. Now applying~\ree{e_omega_Eq3}, we see \beaa \binom{m}{n} &\equiv_p& \prod_{t\in [1,p-1]} t^{\,E_{p,t}(m!)-E_{p,t}(n!)-E_{p,t}((m-n)!)} \nonumber\\ &=\hs{1.4mm}& \prod_{t\in [1,p-1]} t^{\,\sum_{i\ge 0}\left[\chi(m_i\ge t)-\chi(n_i\ge t)-\chi((m-n)_i\ge t)\right]} \label{e_pf_Lucas1}\\ &=\hs{1.4mm}& \prod_{i\ge 0} \prod_{t\in [1,p-1]} t^{\,\chi(m_i\ge t)-\chi(n_i\ge t)-\chi(m_i-n_i\ge t)} \nonumber\\ &=\hs{1.4mm}& \prod_{i\ge 0} t^{\,E_{p,t}(m_i!)-E_{p,t}(n_i!)-E_{p,t}((m_i-n_i)!)} \label{e_pf_Lucas2}\\ &\equiv_p& \prod_{i\ge 0} \binom{m_i}{n_i}. \nonumber \eeaa Among these equivalences and equations, both~\ree{e_pf_Lucas1} and~\ree{e_pf_Lucas2} are due to Lemma~\ref{l_power_p} and three $E'(\cdot)$ canceling each other; the last equivalence is because there is no borrow. \Qed The reader can also find a very neat proof of Lucas' Theorem in~\cite{Fine_02}. That proof is based on the Binomial Expansion Theorem and a simple fact that $p|\binom{p}{r}$ for a prime $p$ and $r=1,2,\ldots,p-1$. Another kind of proof uses induction to substitute the Binomial Expansion Theorem. In contrast, our new proof requires neither. Even more appealing is that our new proofs of Kummer's and Lucas' Theorems are united in a single idea---the concept of $\omega_p$ and $E_{p,t}$. \section{Transforming $\bbZ_{q}^\ast$ to an additive group} \label{s_Zqast_C} For performing the power of $t$ and the product $\prod$ appearing in $CF_p(n!)\equiv_q\prod_{t\in \bbZ_q^\ast} t^{\,E_{q,t}(n!)}$, we need to work on the domain $(\bbZ_q^\ast,\times_q)$ (modulo multiplication group). But operating $\times_q$ is complicated. We simplify this cumbersome operation by transforming $(\bbZ_q^\ast, \times_q)$ to an additive group under isomorphism as follows: \beaa (\bbZ_{2^k}^\ast, \times_q) &\cong& (C_2\times C_{2^{k-2}},+) \text{\quad for $k\ge 2$;} \label{e_Z2k} \\ (\bbZ_{p^k}^\ast, \times_q) &\cong& (C_{p^{k-1}(p-1)},+) \text{\quad for an odd prime $p$,} \label{e_Zpk} \eeaa where $C_m$ represents a cyclic group of order $m$. Please, refer to \cite{Riesel_94} and also see example in Table~\ref{tab_iso} as $q=8, 16, 32, 64$. In the rest of the paper, we focus only on $p=2$. To limit the length of this paper, we will collect the results for an odd prime power modulus in a more extensive paper in the future. \begin{table} \caption{The first few example for the isomorphisms $(\bbZ_{2^k}^\ast, \times_q) \cong (C_2\times C_{2^{k-2}},+)$} \label{tab_iso} \begin{center} $ \begin{tabular}{c|cc} & 0 & 1 \\ \hline 0 & 1 & 5 \\ 1 & 3 & 7 \end{tabular} $ \qquad \qquad $ \begin{tabular}{c|cccc} & 0 & 1 & 2 & 3\\ \hline 0 & 1 & 5 & 9 & 13\\ 1 & 7 & 3 & 15& 11 \end{tabular} $ \end{center} $$ \begin{tabular}{c|cccccccc} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 0 & 1 & 5 & 25 & 29 & 17 & 21 & 9 & 13 \\ 1 & 15 & 11 & 23 & 19 & 31 & 27 & 7 & 3 \end{tabular} $$ $$ \begin{tabular}{c|cccccccccccccccc} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline 0 & 1 & 5 & 25 & 61 & 49 & 53 & 9 & 45 & 33 & 37 & 57 & 29 & 17 & 21 & 41 & 13 \\ 1 & 31 & 27 & 7 & 35 & 47 & 43 & 23 & 51 & 63 & 59 & 39 & 3 & 15 & 11 & 55 & 19 \end{tabular} $$ \end{table} The multiplication in $(\bbZ_{q}^\ast,\times_q)$ is then easily carried out through the corresponding addition in $(C_2\times C_{2^{k-2}},+)$. For instance, \bea 7^5\times_{16} 11^{15} &\equiv_{16}& {T_{16}}^{-1}(5\,T_{16}(7)+15\,T_{16}(11))\\ &\equiv_{16}& {T_{16}}^{-1}(5\,(1,0)+15\,(1,3))\\ &\equiv_{16}& {T_{16}}^{-1}((1,0)+(1,1))\\ &\equiv_{16}& {T_{16}}^{-1}((0,1))\\ &\equiv_{16}& 5, \eea where $T_{16}$ is the isomorphism from $\bbZ_{16}^\ast$ to $C_2\times C_{4}$ demonstrated in Table~\ref{tab_iso}. Let $q=2^k$. The isomorphism $$ T_q: (\bbZ_{q}^\ast,\times_q) \ra (C_2\times C_{q/4},+) \text{ for $k\ge 2$,} $$ is constructed as follows. We use $\bx$ or $(b,u)$ to denote an element of $C_2\times C_{q/4}$, and define $T_q(t):=\bx(t)= (b(t),u_q(t))$. As notation, $b(t)$ has no subscript $q$ for a reason that will be explained latter. The most trivial case is $T_4$ such that $b(1)=0$, $b(3)=1$ and $u_4(t)\equiv 0$, a constant function. We assume $k\ge 3$ in this paragraph only. Define $\bbZ_{q}^{\ast,1}:= \{t\in \bbZ_{q}^\ast \mid t\equiv_4 1\}$ and $\bbZ_{q}^{\ast,3}:= \{t\in \bbZ_{q}^\ast \mid t\equiv_4 3\}$. Clearly, $\bbZ_{q}^{\ast,1}$ is a subgroup of $\bbZ_{q}^{\ast}$ and $\bbZ_{q}^{\ast,3}$ is the unique coset. It is also easy to prove by induction that $[5^{(2^{k-2})}]_2=\fall{\cdots 1\underbrace{0\cdots 0}_{ \textrm{$k-1$ zeros}} 1}{2}\equiv_{2^k} 1$ and $\bbZ_{q}^{\ast,1}$ is a cyclic group with $5$ as a generator. Therefore, we can make \bea T_q(\bbZ_{q}^{\ast,1}) &=& \{(0,u)\mid u\in C_{q/4}\} \text{ with } T_q(5)=(0,1), \text{ and}\\ T_q(\bbZ_{q}^{\ast,3}) &=& \{(1,u)\mid u\in C_{q/4}\}. \eea The reason of no subscript $q$ for $b(t)$ is now clear, because we must have \beq \label{e_bt} b(t) = \left\{ \barr{l@{\quad}l} 0 & \text{ if $t\equiv_4 1$}\\ 1 &\text{ if $t\equiv_4 3$} \earr \right\} = t_1 \text{\quad where $[t]_2=\fall{\cdots t_2 t_1 1}{2}$,} \eeq which is independent on $q$. The isomorphism $u_q: \bbZ_{q}^{\ast,1} \ra C_{q/4}$ is now well defined by $u_q(5)=1$. Precisely, $u_q(t)$ equals the minimal nonnegative integer $u$ such that $5^u\equiv_q t$. As for those $t\in \bbZ_{q}^{\ast,3}$, let $\hat{t}\in \bbZ_{q}^{\ast,1}$ be the unique element satisfying $t+\hat{t}\equiv_q q/2$ and then define $u_q(t):= u_q(\hat{t})$. We leave the check that $T_q$ is really an isomorphism to the reader. Let us extend the domain of $u_q$ from $\bbZ^\ast_{q}$ to $\bbZ_{\text{o}}$, the set of odd integers, by simply defining $u_q(t):= u_q(t\pmod{q})$ for any odd integer $t$. The following are three fundamental formulae about $u_q$. \ble \label{l_uq_uq} Given integers $k'>k\ge 2$ and $q':=2^{k'}, q:=2^k$, we have \beqq \barr{rlll} u_{q'}(t)\pmod{\frac{q}{4}} & = & u_q(t) & \text{\quad for any $t\equiv_4 1$;}\\ u_{q'}(t)\pmod{\frac{q}{8}} & = & u_q(t) \pmod{\frac{q}{8}} & \text{\quad for any $t\equiv_4 3$ and $k\ge 3$;}\\ u_{q'}(t)\pmod{\frac{q}{4}} & = & u_q(t) + \frac{q}{8}\chi & \text{\quad for any $t\equiv_4 3$ and $k\ge 3$,} \earr \eeqq where $\chi$ is either $0$ or $1$. \ele \pf The assertion can be more general by plugging two odd integers $t',t\in\bbZ_{\text{o}}$ with $t'\equiv_q t$ into the both sides of each equation respectively. In case that $t', t\equiv_4 1$, by definition $5^{u_{q'}(t')}\equiv_{q'} t' \equiv_{q} t \equiv_{q} 5^{u_{q}(t)}$ or $5^{u_{q'}(t')}\equiv_{q} 5^{u_{q}(t)}$ in short. Since $5$ is a generator of $\bbZ^{\ast,1}_q$ with order $\frac{q}{4}$. Thus, $u_{q'}(t')\equiv_{q/4} u_{q}(t)$ and the first equation (not equivalence) holds because $u_{q}(t)\in [0,\frac{q}{4}-1]$. Suppose $t'\equiv_q t$ and both $t', t\equiv_4 3$. We find the two numbers $\hat{t'}, \hat{t}\equiv_4 1$ with $\hat{t'} \equiv_{q'} \frac{q'}{2}-t'$ and $\hat{t} \equiv_q \frac{q}{2}-t$, so that $u_{q'}(t'):= u_{q'}(\hat{t'})$ and $u_{q}(t):= u_{q}(\hat{t})$ by definition. Clearly, $\hat{t'} \equiv_{q/2} \hat{t}$; so we can plug these two respectively into the both sides of the first equation of the lemma. Thus, we get $u_{q'}(\hat{t'}) \pmod{\frac{q}{8}} =u_{q/2}(\hat{t})$ and then reach the general version of the second equation of the lemma as follows $$ u_{q'}(t')\pmod{\frac{q}{8}} =u_{q/2}(t) = u_{q}(t)\pmod{\frac{q}{8}}, $$ where the second equation is a special case of the first one provided that $t'=t$ and $q'=q$. The last equation of the lemma is a direct result of the second one. \Qed Directly from Table~\ref{tab_iso}, we have \beq \label{e_u8t} \barr{rll} u_8(t) &=& t_2, \text{ and} \\ u_{16}(t) &=& t_1+ t_2+ 2t_3- 2t_1t_2. \earr \eeq The greater the power $q=2^k$, the more complicated $u_q(t)$ is. Comparing with the complication of the second entry in $T_q(t)=(b(t), u_q(t))$, the inverse ${T_q}^{-1}$ is much easier to describe as follows: \beq \label{e_Rq-1} {T_q}^{-1}(b,u) \equiv_q \left\{ \barr{ll} 5^u & \text{if $b=0$} \\ 2^{k-1}-5^u & \text{if $b=1$} \earr \right\} \equiv_q 2^{k-1}b+(-1)^b 5^u \quad \text{for $k\ge 2$}. \eeq \subsection*{$T_{2^k}(CF_2(n!))$ and $T_{2^k}(CF_2(c_n))$} \label{ss_Rq_Qq} The argument in this subsection will show a difference in $T_{p^k}(CF_p(\cdot))$ between the cases $p=2$ and $p$ being an odd prime. This is another reason why we divide our discussion into two papers. Let us extend the domain of $u_q$ from $\bbZ^\ast_{q}$ to the set of odd integers, by simply define $u_q(t):= u_q(t\pmod{q})$. In general, we have \beaa T_q(CF_2(\prod_{i=1}^a M_i)) &=& \sum_{t\in \bbZ_q^\ast} E_{q,t}(\prod_{i=1}^a M_i)\,T_q(t) \label{e_sum_Eq_Rq} \\ &=& \sum_{\bx \in C_2\times C_{q/4}} E_{q,{T_q}^{-1}(\bx)}(\prod_{i=1}^a M_i)\,\bx. \label{e_sum_Eq_cx} \eeaa Any term of $E_{q,t}(\prod_{i=1}^a M_i)$ that is independent on $t$ finally contributes $(0,0)$ in total to the above summation due to a simple algebraic property as follows: \beq \label{e_u00} \sum_{\bx\in C_2\times C_{q/4}} \bx= |C_{q/4}|\sum_{b\in C_{2}} (b,0) + |C_2| \sum_{u\in C_{q/4}} (0,u) = 2^{k-2}(1,0)+2\,(0,2^{k-3})=(0,0), \eeq when $k\ge 3$. A corresponding property is that \beq \label{e_u01} \prod_{t\in \bbZ_{2^k}^\ast} t= 1 \quad \textrm{for $k\ge 3$ or $k=1$.} \eeq By Lemma~\ref{l_power_p}, the partial term $E'_q(n!)$ is independent on $t$; so we have $\sum_{\bx\in C_2\times C_{q/4}} E'_q(n!)\,\bx=(0,0)$ and we can ignore $E'_q(n!)$. Thus, if the formal product is $n!$, we improve~\ree{e_sum_Eq_Rq} by a better formula as follows: \beq \label{e_sum_Eq_Rq2} T_q(CF_p(n!)) = (b(CF_p(n!), u_q(CF_p(n!)) = \sum_{t\in \bbZ_q^\ast} E''_{q,t}(n!)\,(b(t),u_q(t)). \eeq However, the property~\ree{e_u01} fails when $k=2$ or $p$ is an odd prime; so \ree{e_sum_Eq_Rq2} does not work in this condition. As for $k=2$, not only the isomorphism $\bbZ_{4}^\ast\cong C_2$ is trivial, but also \beq \label{e_E43} CF_2(n!)\equiv_4 (-1)^{E_{4,3}(n!)}=(-1)^{r(n)+n_{_0}+n_{_1}}=(-1)^{d_{_2}(n)+c_{_2}(n)}, \eeq shown by Lemma~2.1 in~\cite{Eu_Liu_Yeh_07}, is a easy formula. Apart from $n_0$, $n_1$ and $d_{_2}$, we have not defined some new notation in~\ree{e_E43} yet. Over the sequence $[n]_2$, let $r(n)$ be the number of runs of $1$, and let $c_{_2}(n):= \sum_{i\ge 0} \chi(n_i=n_{i+1}=1)$, i.e., the number of the consecutive pairs of $1$. The last equality in~\ree{e_E43} is due to the simple fact that $c_{_2}(n)=d(n)-r(n)$. By~\ree{e_bt} and~\ree{e_E43}, we conclude that \beq \label{e_bCF_nfac} b(CF_2(n!)) \equiv_2 r(n)+n_0+n_1 \equiv_2 d_2(n)+c_{_2}(n) \equiv_2 zr(n)+n_1. \eeq The last equivalence will be explained later in~\ree{e_CF8n2}. In the following three sections, we develop formulae of $T_q(CF_p(n!))$ for $q=8, 16, 32$ and $64$, and also to evaluate the Catalan number, $c_n$, modulo $8$, $16$ and $64$. (We skip $32$.) The problem of $c_n$ (mod $2$) can be easily solved by Lucas' Theorem. For the problem of $c_n$ (mod $4$), please refer to~\cite{Eu_Liu_Yeh_07}. \section{$b(CF_2(n!))$ and $u_8(CF_2(n!))$; Catalan numbers modulo $8$} \label{s_bu8_cm8} Given a multi-subset $\cM$ and a subset $T$ of $\bbZ_q$, let $\#(\cM,T)$ be the number of elements (with multiplicity) in $\cM$ belonging to $T$. Define a multi-set $$ \cS_k(n):=\{|\fall{n_{k+i-1}\dots n_{i+1}n_i}{2}|\}_{i=0}^r, $$ where $[n]_2=\fall{n_r\cdots n_1 n_0}{2}$ and $\fall{n_{k+i-1}\dots n_{i+1}n_i}{2}$ is a $k$-\emph{segment} contained in the sequence $\langle \overbrace{0\cdots00}^{k-1}n_r\cdots$ $n_1n_0\rangle_{2}$. For example, given $[n]_2=\fall{100110000101}{2}$ we have $\cS_3(n):=\{5,2,1,0,0,$ $4,6,3,1,4,2,1\}$ if we check all $k$-segments from right to left, and $\#(\cS_3(n),\{3,4\})=3$. The following counting formulae for $\#(\cS_3(n),\{t\})$ are easy to check. \beaa \#(\cS_3(n),\{3\}) &=& \sum_{i\ge 0} \chi(\langle n_{i+2}n_{i+1}n_i \rangle = \langle 011 \rangle)\ =\ r(n)-r_1(n); \label{e_cS3_3} \\ \#(\cS_3(n),\{4\}) &=& \sum_{i\ge 0} \chi(\langle n_{i+2}n_{i+1}n_i \rangle = \langle 100 \rangle)\ =\ zr(n)-zr_1(n); \label{e_cS3_4} \\ \#(\cS_3(n),\{5\}) &=& \sum_{i\ge 0} \chi(\langle n_{i+2}n_{i+1}n_i \rangle = \langle 101 \rangle)\ =\ zr_1(n)-n_1(1-n_0); \nonumber\\ \#(\cS_3(n),\{6\}) &=& \sum_{i\ge 0} \chi(\langle n_{i+2}n_{i+1}n_i \rangle = \langle 110 \rangle)\ = r(n)-r_1(n)-n_0n_1, \nonumber \eeaa where $r_1(n)$ is the number of isolated $1$ in $[n]_2$, $zr(n)$ the number of runs made by $0$, and $zr_1(n)$ the number of isolated $0$. Referring to~\ree{e_E_2prime}, \ree{e_sum_Eq_Rq2} and Table~\ref{tab_iso} for $\bbZ_{8}^\ast \cong C_2\times C_{2}$, we derive \bea E''_{8,3}(n!)\,(1,0) &=& (\sum_{i\ge 0} \chi(|\langle n_{i+2} n_{i+1}n_i\rangle_p| \ge 3),0)\ = \ (\#(\cS_3(n),\{3,4,5,6,7\}),0),\\ E''_{8,5}(n!)\,(0,1) &=& (0,\sum_{i\ge 0} \chi(|\langle n_{i+2} n_{i+1}n_i\rangle_p| \ge 5)\ = \ (0, \#(\cS_3(n),\{5,6,7\})), \text{ and}\\ E''_{8,7}(n!)\,(1,1) &=& \Big[\sum_{i\ge 0} \chi(|\langle n_{i+2} n_{i+1}n_i\rangle_p| \ge 7)\Big] (1,1)\ = \ (\#(\cS_3(n),\{7\}), \#(\cS_3(n),\{7\})). \eea Summing up the above three, we obtain \beaa T_8(CF_2(n!)) &=& (b(CF_2(n!)),u_8(CF_2(n!))) \nonumber \\ &=& (\#(\cS_3(n),\{3,4,5,6\}),\, \#(\cS_3(n),\{5,6\}))\hs{-2mm}\pmod{2} \label{e_CF8n3}\\ &=& (zr(n)+n_1,\, r(n)+r_1(n)+zr_1(n)+n_1)\hs{-2mm}\pmod{2} \label{e_CF8n2} \\ &=& (r(n)+n_0+n_1,\, r(n)+r_1(n)+zr_1(n)+n_1)\hs{-2mm}\pmod{2}. \label{e_CF8n} \eeaa The last equation is due to the fact $r(n)=zr(n)+n_0$. This equation also explains the last equivalence in~\ree{e_bCF_nfac}. Again we see the fact that $b(CF_2(n!))$ is independent on $q$. In the rest of this section, we re-prove the following theorem, which was first shown in~\cite{Eu_Liu_Yeh_07}, through an easier approach. \bth[Eu, Liu and Yeh, 2008~\cite{Eu_Liu_Yeh_07}] \label{t_ELY_Cat8} Let $c_n$ be the $n$-th Catalan number. Then $c_n \not\equiv_8 3, 7$ for any $n$. And for the other congruences, we have \begin{equation*} c_n \equiv_8 \left\{ \barr{ll} 1 & \textit{if\quad $n=0$ or $1$;}\\ 2 & \textit{if\quad $n=2^a+2^{a+1} -1$ for some $a\ge 0$;}\\ 4 & \textit{if\quad $n=2^a+2^b+2^c-1$ for some $c>b>a\ge 0$;}\\ 5 & \textit{if\quad $n=2^a-1$ for some $a\ge 2$;}\\ 6 & \textit{if\quad $n=2^a+2^b-1$ for some $b-2\ge a\ge 0$;}\\ 0 & \textit{otherwise.} \earr \right. \end{equation*} \eth We first discuss some general properties for modulus $q=2^k$. Since $c_n = \frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{(n+1)(n!)^2}$, by Lemma~\ref{l_power_p} we have \bea \omega_2(c_n) &=& [2n-d(2n)]-\omega_2(n+1)-2[n-d(n)]\\ &=& 2n-d(n)-\min\{i\mid n_i=0\}-2n+2d(n)\\ &=& d(n)-\min\{i\mid n_i=0\}\\ &=& d(n+1)-1. \eea The last equation is due to the fact that $\min\{i\mid n_i=0\}$ is the length of the run of $1$ starting at the $0$-th place of $[n]_2$. In the process of proving Theorem~\ref{t_ELY_Cat8}, the above result for $\omega_2(c_n)$ provides a new proof of the next theorem. \bth[Deutsch and Sagan, 2006~\cite{Deutsch_Sagan_06}] \label{t_DeuSag_omegaCat} For $n\in \bbN$ we have \beqq \label{e_omega_cn} \omega_2(c_n)= d(n+1)-1 = d(n)-\min\{i\mid n_i=0\}. \eeqq \eth When we deal with $c_n$ modulo $2^k$, this theorem suggests that $[n]_2$ be bisected into two particular segments as follows: \beq \label{e_n_form_cn} \langle \overbrace{10\cdots 1100}^{\rlap{\text{\scriptsize The rightmost is a $0$.}}}\ \ \underbrace{1\cdots 1}_{\rlap{\text{\scriptsize This segment of all $1$ might be empty.}}} \rangle_2 \eeq We call these two segments the \emph{principal segments} of $[n]_2$ and use $[2\al]_2$ and $\fall{1^\be}{2}$ to denote them respectively, where $\al,\be \in \bbN$ and $1^\be$ means a string of $1$ of length $\be$. We use $2\al$ because its $0$-th place digit must be $0$. Equivalently, we can also define \bea \al &:=& \frac{CF_2(n+1)-1}{2}, \text{ and} \\ \be &:=& \omega_2(n+1) = \min\{i\mid n_i=0\}. \eea Here we find that the notation $\al$ is good to use in the following property which directly follows Theorem~\ref{t_DeuSag_omegaCat}. \bco \label{c_Cat_2_k-1} In general, we have $\omega_2(c_n)=d(\al)$. In particular, $c_n\equiv_q 0$ if and only if $d(\al)\ge k$, and $c_n\equiv_q q/2$ if and only if $d(\al)= k-1$. \eco Due to this corollary, from now on we focus only on $d(\al)\le k-2$. Let us examine $T_8(CF_2(n!))$. Its first entry is enumerated by using~\ree{e_bt} and~\ree{e_bCF_nfac} as follows: \beaa b(CF_2(c_n)) &\equiv_2& [zr(2n)+(2n)_1] - b(CF_2(n+1)) -2 [zr(n)+n_1]\nonumber \\ &\equiv_2& [(zr(n)+n_0)+n_0] + b(2\al+1)\nonumber \\ &\equiv_2& zr(n)+\al_0\nonumber \\ &\equiv_2& (zr(\al)+\al_0)+\al_0 \nonumber\\ &\equiv_2& zr(\al). \label{e_bCF_cn} \eeaa Since $b(CF_2(c_n))$ is independent on $q$, this identity derives a general formula as follows. \bth \label{t_cn_mod_q_1} Let $n\in \bbN$, $q=2^k$ with $k\ge 2$, and $\al= (CF_2(n+1)-1)/{2}$. Then we have \beq \label{e_cn_mod_q_1} c_n \equiv_q (-1)^{zr(\al)} 2^{d(\al)} 5^{u_q(CF_2(c_n))}. \eeq In particular, when $k= 2$ we have \beq \label{e_cn_mod_qq} c_n \equiv_4 (-1)^{zr(\al)} 2^{d(\al)}. \eeq \eth \pf By~\ree{e_Rq-1}, Theorem~\ref{t_DeuSag_omegaCat} (or Corollary~\ref{c_Cat_2_k-1}) and the result of $b(CF_2(c_n))$ in~\ree{e_bCF_cn}, we have \bea c_n &\equiv_q& 2^{\omega_2(c_n)} \big[ 2^{k-1} b + (-1)^b 5^u \big]\\ &\equiv_q& 2^{d(\al)} \big[ 2^{k-1} zr(\al)+ (-1)^{zr(\al)} 5^{u_q(CF_2(c_n))} \big]. \eea We finish the proof of the first assertion after considering two cases: $d(\al)=0$ (which implies $zr(\al)=0$) and $d(\al)\ge 1$. Notice that $u_4(t)= 0$ and then the second assertion follows. \Qed The equivalence~\ree{e_cn_mod_qq} is actually a rewrite of Eu, Liu and Yeh's result in~\cite{Eu_Liu_Yeh_07}. The immediate consequence that $c_n \not\equiv_4 3$ was also given by them. The following two auxiliary corollaries directly follows Theorem~\ref{t_cn_mod_q_1}. \bco \label{c_cn_eq} Let $n,k\in \bbN$ with $k\ge 3$, $\al= (CF_2(n+1)-1)/{2}$ and $d(\al)= k- 2$. We have \beqq c_n \equiv_q (-1)^{zr(\al)} \frac{q}{4}. \eeqq \eco \bco \label{c_CF2cn_mod4} Let $n\in \bbN$ and $\al= (CF_2(n+1)-1)/{2}$. We have \beqq CF_2(c_n) \equiv_4\ (-1)^{zr(\al)}. \beqq \eco \noindent Corollary~\ref{c_cn_eq} solves the case $d(\al)= k-2$ and is an improvement of Corollary~\ref{c_Cat_2_k-1}. We will deal with the case $d(\al)= k-3$ by Corollary~\ref{c_cn_eq16} in the next section. Formula~\ree{e_cn_mod_q_1} offers a general method to enumerate $c_n$ (mod $2^k$), but it does not offer the classification like Theorem~\ref{t_ELY_Cat8}. On the other hand, Table~\ref{tab_iso} provides an easier way without calculating $5^{u_q}$ when $k$ is small. We use the second way to classify $c_n$ modulo $8$, $16$ and $64$. However, the enumeration of $u_q(CF_2(c_n))$ is crucial through either way. The formula for $u_q(CF_2(c_n))$ of course depends on $q$ and the large is $k$, the more complicated is it. Fortunately, what we need here is $u_8(CF_2(c_n))$ which is quit easy as follows: \beaa u_8(CF_2(c_n)) &\equiv_2& [r(2n)+ r_1(2n)+ zr_1(2n)+ (2n)_1]- u_8(CF_2(n+1))\\ &&\quad -2[r(n)+ r_1(n)+ zr_1(n)+ n_1] \nonumber\\ &\equiv_2& r(n)+ r_1(n)+ [zr_1(n)+n_0-n_1(1-n_0)]+ n_0+ u_8(2\al+1) \nonumber\\ &=& [r(\al)+\chi(\be\ge 1)]+ [r_1(\al)+\chi(\be=1)]+ [zr_1(\al)+ \al_0 -\al_1(1-\al_0)] \nonumber\\ &&\quad -[\chi(\be\ge 2)+ \chi(\al=1)\chi(\be=0)]\chi(\be=0) + \al_1 \nonumber\\ &\equiv_2& \chi(\be\ge 2)+\chi(\al=1,\be=0) +r(\al) +r_1(\al) +zr_1(\al) +\al_0(1- \al_1). \label{e_u8cn} \eeaa By the formula of $u_8(CF_2(c_n))$, we can finish the mission of this section. Let us rewrite Theorem~\ref{t_ELY_Cat8} in a new format using $\al$ and $\be$ as follows. The equivalence of these two theorems is easy to check. \bth \label{t_ELY_Cat8a} Given $n\in \bbN$, let $\al= \frac{CF_2(n+1)-1}{2}$ and $\be= \min\{i\mid n_i=0\}$. We have \begin{equation*} c_n \equiv_{8} \left\{ \barr{l@{\quad\text{if}\quad}l} \left. \barr{r} 1\\ 5 \earr \right\} & \textit{$d(\al)=0$ and \quad} \left\{ \barr{l} \be=0 \text{ or } 1,\\ \be\ge 2, \earr \right. \\ \left. \barr{r} 2\\ 6 \earr \right\} & \textit{$d(\al)=1$ and \quad} \left\{ \barr{l} \al= 1,\\ \al\ge 2, \earr \right. \\ \left. \barr{r} 4 \earr \right. & \textit{$d(\al)=2$,}\\ \left. \barr{r} 0 \earr \right. & \textit{$d(\al)\ge 3$.} \earr \right. \end{equation*} \eth \pf The congruences $0$, $2$, $4$ and $6$ can be easily solved by Corollaries~\ref{c_Cat_2_k-1} and~\ref{c_cn_eq}. The only remaining case is $d(\al)=0$. In this case, every term related to $\al$ turns to be $0$ in~\ree{e_u8cn}. Then plug into~\ree{e_cn_mod_q_1} and obtain $$ c_n \equiv_8 (-1)^{0} 2^{0} 5^{\chi(\be\ge 2)} \equiv_8 5^{\chi(\be\ge 2)}. $$ Therefore, $c_n\equiv_8 1$ if and only if $[n]_2=\fall{1}{2}$ or it is an empty sequence, and $c_n\equiv_8 5$ if and only if $[n]_2=\fall{1^\be}{2}$ for $\be\ge 2$. The proof is complete now. \Qed \section{$u_{16}(CF_2(n!))$; Catalan numbers modulo $16$} \label{s_u16_cm16} Since we already know $\omega(c_n)=d(\al)$ and $b(CF_2(c_n))=zr(\al)$, to enumerate $c_n$ (mod $q$) now relies on $u_q(CF_2(c_n))$, which depends on $u_q(CF_2(n!))$ further. Of course, directly dealing with modulus $64$ will fill the unsolved gape for both moduli $16$ and $32$; however, when $q$ is larger $u_q(CF_2(n!))$ becomes more complicated. In order to deal with modulus $64$ smoothly, we consider solving the problem of $c_n$ (mod $16$) as a necessary practice and preparation. First of all, we state a general formula of $u_{q}(CF_2(n!))$ for any $q=2^k$. By~\ree{e_E_2prime} and~\ree{e_sum_Eq_Rq2}, we derive that \beaa u_{q}(CF_2(n!)) &\equiv_{q/4}& \sum_{t\in \bbZ_q^\ast}E''_{q,t}(n!) \, u_q(t) \nonumber \\ &=& \sum_{t\in \bbZ_q^\ast} \chi(|\fall{ n_{i+k-1}\cdots n_{i+1}n_i}{2}| \ge t)\, u_q(t) \nonumber \\ &=& \sum_{t\in \bbZ_q^\ast} \#(\cS(n),[t,q-1])\, u_q(t) \nonumber \\ &=& \sum_{s\in [1,q-1]} \#(\cS(n),\{s\})\sum_{t\in [1,s]_{\text{o}}} u_q(t)\label{e_uq_CF2a}\\ &=& \sum_{s\in [3,q-2]} \#(\cS(n),\{s\})\sum_{t\in [3,s]_{\text{o}}} u_q(t) \label{e_uq_CF2}\\ &=& \sum_{s\in [3,q-3]_{\text{o}}} \#(\cS(n),\{s,s+1\})\sum_{t\in [3,s]_{\text{o}}} u_q(t) \label{e_uq_CF2c} \eeaa where $[1,s]_{\text{o}}$ is the set of odd integers in $[1,s]$. Note that $\sum_{t\in [1,s]_{\text{o}}} u_q(t)=\sum_{t\in [3,s]_{\text{o}}} u_q(t)$ for $u_q(1)=0$. For this reason, we eliminate $s=1,2$ in the first summation of~\ree{e_uq_CF2a}. Moreover, we eliminate $s=q-1$ because $\sum_{t\in [1,q-1]_{\text{o}}} u_q(t) = 0$ (see the second entry in~\ree{e_u00}). The last formula~\ree{e_uq_CF2c} is because $\sum_{t\in [3,s]_{\text{o}}} u_q(t)=\sum_{t\in [3,s+1]_{\text{o}}} u_q(t)$ for any odd $s$. Depending on $k$, there are several kinds of $k$-segments (we mean $[t]_2$ for $t\in [0,q-1]$) irrelevant to the counting in~\ree{e_uq_CF2}. For example, we see in~\ree{e_CF8n3} that $u_{8}(CF_2(n!))$ only counts on the $3$-segments $[5]_2$ and $[6]_2$ appearing in $[n]_2$, and it is irrelevant to the other $3$-segments. However, we shall only focus on the two kinds of $k$-segments of irrelevance that are independent on $k$, i.e., $[0]_2=\fall{0^k}{2}$ and $[q-1]_2=\fall{1^k}{2}$. Because of the irrelevancy of these two kinds of $k$-segments appearing in $[n]_2$, we conclude an important property as follows: \bth \label{t_n_tn} Given $n\in\bbN$, let $m$ be an integer such that $[m]_2$ is obtained by either extending or truncating some runs of $0$ or $1$ of length $\ge k-1$ in $[n]_2$ to be different length but still $\ge k-1$. We have $b(CF_2(n!))=b(CF_2(m!))$ and $u_{q}(CF_2(n!)) = u_{q}(CF_2(m!))$, and then $$ CF_2(n!) \equiv_{q} CF_2(m!). $$ \eth \pf The proof of the second identity was stated in head of the theorem. The first one is due to the fact $b(CF_2(n!))\equiv_2 zr(n)+n_1$ together with $zr(n)=zr(m)$ and $n_1=m_1$. The last equivalence is a direct consequence. \Qed We use $\dot{n}$ to denote the integer such that $[\dot{n}]_2$ is obtained by truncating every run of $1$ of length $\ge k$ in $[n]_2$ to be exactly length $k-1$, without changing any run of $0$. Also let $\ddot{n}$ is the number obtained by truncating every run of $0$ and run of $1$ by the same way. For instance, let $k=3$ and $[n]_2=\fall{100011101111}{2}$ then $[\dot{n}]_2=\fall{100011011}{2}$ and $[\ddot{n}]_2=\fall{10011011}{2}$. Note that both $\dot{n}$ and $\ddot{n}$ depend on $k$, but we do not mark $k$ for convenience. To avoid confusion, it should be remembered which $k$ is discussed. From~\ree{e_uq_CF2}, let us use the isomorphism $\bbZ_{16}^\ast \cong C_2\times C_{4}$ in Table~\ref{tab_iso} to construct a new table as follows: $$ \begin{tabular}{c|cccccc} $s\in [3,13]_{\text{o}}\sbe \bbZ_{16}^\ast$ & 3 & 5 & 7 & 9 &11 &13 \\ \hline $u_{16}(s)\in C_{4}$ & 1 & 1 & 0 & 2 & 3 & 3 \\ $\sum_{t\in [3,s]_{\text{o}}} u_{16}(s)\hs{-2mm} \pmod{4}$ & 1 & 2 & 2 & 0 & 3 & 2 \end{tabular} $$ The last row of this table records the accumulations according to the second row. Now plug these accumulations into~\ree{e_uq_CF2c} and Lemma~\ref{t_n_tn} to obtain \beaa u_{16}(CF_2(n!)) &\equiv_4& \#(\cS_4(\dot{n}), \{3,4\}) +2\#(\cS_4(\dot{n}), \{5,6,7,8,13,14\}) +3\#(\cS_4(\dot{n}),\{11,12\})\nonumber\\ &=& \#(\cS_4(\dot{n}), \{3,4,5^2,6^2,7^2,8^2,11^3,12^3,13^2,14^2\}) \label{e_u16_nfac1} \eeaa where the second line is a comprehensible modification for $\#(\cdot,\cdot)$ as weighted counting according each superscript. Notice that the weights of $t$ (odd) and $t+1$ (even) are the same. Also notice that we can replace $\dot{n}$ with $\ddot{n}$ in this formula. Since formula~\ree{e_u16_nfac1} is still too rough to use, we partition it into four disjoint parts and then simplify them. In the following, we consider $[t]_2$ and $t$ the same element to plug into $\#(\cS_4(\dot{n},\{\cdot\})$, and $\text{x}$ means an unspecified binary digit. \beaa A &:=& \#(\cS_4(\dot{n}), \{4\}) +2\#(\cS_4(\dot{n}), \{5,6,7\}) \nonumber \\ &=& \#(\cS_4(\dot{n}), \{\fall{0100}{2}\}) +2\big[ \#(\cS_4(\dot{n}), \{\fall{01\text{xx}}{2}\})- \#(\cS_4(\dot{n}), \{\fall{0100}{2}\}) \big] \nonumber \\ &=& 2r(\fl{\frac{\dot{n}}{4}})-\#(\cS_4(\dot{n}),\{\fall{0100}{2}\}) \nonumber\\ &=& 2[r(\dot{n})-\dot{n}_1(1-\dot{n}_2)-\dot{n}_0(1-\dot{n}_1)]- \#(\cS_4(\dot{n}),\{\fall{0100}{2}\}); \nonumber \eeaa \beaa B &:=& 3\#(\cS_4(\dot{n})\{12\})+ 2\#(\cS_4(\dot{n}), \{13,14\}), \nonumber\\ &=& 3\#(\cS_4(\dot{n})\{\fall{1100}{2}\}) +2 \big[ \#(\cS_4(\dot{n}), \{\fall{11\text{xx}}{2}\})- \#(\cS_4(\dot{n}), \{\fall{1100}{2}\}) \big] \label{e_1100}\\ &=& 2\#(\cS_4(\dot{n}), \{\fall{11\text{xx}}{2}\}) + \#(\cS_4(\dot{n})\{\fall{1100}{2}\})\nonumber\\ &=& 2c_{_2}(\fl{\frac{\dot{n}}{4}})+\#(\cS_4(\dot{n}),\{\fall{1100}{2}\}) \nonumber\\ &=& 2[c_{_2}(\dot{n})-\dot{n}_0\dot{n}_1-\dot{n}_1\dot{n}_2]+\#(\cS_4(\dot{n}), \{\fall{1100}{2}\}); \nonumber\\ C &:=& \#(\cS_4(\dot{n}), \{3\})- \#(\cS_4(\dot{n}), \{11\})\nonumber\\ &=& \#(\cS_4(\dot{n}), \{\fall{0011}{2}\})- \big[ \#(\cS_4(\dot{n}), \{\fall{\text{x}011}{2}\})- \#(\cS_4(\dot{n}), \{\fall{0011}{2}\})\big] \nonumber\\ &=& 2\#(\cS_4(\dot{n}), \{\fall{0011}{2}\})- \#(\cS_3(\dot{n}), \{\fall{011}{2}\}) \nonumber\\ &=& 2\#(\cS_4(\dot{n}), \{\fall{0011}{2}\})- r(\dot{n}) +r_1(\dot{n}); \label{e_0011}\\ D &:=& 2\#(\cS_4(\dot{n}), \{8\}) \nonumber\\ &=& 2\#(\cS_4(\dot{n}), \{\fall{1000}{2}\}) \nonumber \eeaa We obtain~\ree{e_1100} because $\fall{11\text{xx}}{2}$ has four types $[12]_2$, $[13]_2$, $[14]_2$, and $[15]_2=\fall{1111}{2}$, but $15$ never appears in $\cS_4(\dot{n})$ for the truncation property of $\dot{n}$. We obtain~\ree{e_0011} by referring to~\ree{e_cS3_3}. Now collecting the four results above with a simple arrangement and referring to~\ree{e_cS3_4}, we obtain \beaa u_{16}(CF_2(n!)) &\equiv_4& u_{16}(CF_2(\dot{n}!)\\ &\equiv_4& 2\big[r(\dot{n})+c_{_2}(\dot{n})+ \dot{n}_0+ \dot{n}_1+ \#(\cS_4(\dot{n}), \{\fall{0011}{2},\fall{1100}{2},\fall{1000}{2}\}) \big]\nonumber \\ &&\quad + r_1(\dot{n})- r(\dot{n}) -\#(\cS_4(\dot{n}),\{\fall{0100}{2},\fall{1100}{2}\}) \nonumber \\ &=& 2\big[c_{_2}(\dot{n})+ \dot{n}_0+ \dot{n}_1+ \#(\cS_4(\dot{n}), \{\fall{0011}{2},\fall{1\text{x}00}{2}\}) \big]\nonumber \\ &&\quad + r_1(\dot{n})+ r(\dot{n}) + zr_1(\dot{n})-zr(\dot{n}). \label{e_u16_nfac} \eeaa \noindent{\bf Remark.}\quad In~\ree{e_1100}, we do use the property that $[\dot{n}]_2$ contains no sub-sequence $\fall{1^4}{2}$, whereas it does not matter for the existence of $\fall{0^4}{2}$ in $[\dot{n}]_2$. Therefore, to apply~\ree{e_u16_nfac}, truncating every run of $1$ in $[n]_2$ is compulsory; however, truncating a run of $0$ is optional. In other words, we can truncate or extend any run of $0$ as long as we maintain the length $\ge k-1$. We are ready to develop $u_{16}(CF_2(c_n))$. For this problem, we interpret $[n]_2$ as its two segments $[2\al]_2$ and $\fall{1^\be}{2}$ defined in~\ree{e_n_form_cn}. Similarly, $[\dot{n}]_2$ also has its own two principal segments, which shall be $[2\dot{\al}]_2$ and $\fall{1^{\be'}}{2}$ with $\be'=\min\{\be,3\}$. We have $$ u_{16}(CF_2(n+1))=u_{16}(2\al+1)= u_{16}(2\dot{\al}+1)=u_{16}(CF_2(\dot{n}+1)), $$ where the two $u_{16}$'s are equal because they depend respectively on the identical $3$-segments $\fall{\al_2\al_1\al_0}{2}$ and $\fall{\dot{\al}_2\dot{\al}_1\dot{\al}_0}{2}$ (see~\ree{e_u8t}). This is why we use $\dot{n}$ instead of $\ddot{n}$. Actually, the only situation we are concerned about is that $\al\neq 0$ and $\fall{\al_2\al_1\al_0}{2}=\fall{000}{2}$. For instance, let $[n]_2=\fall{100001}{2}$, and so $[\dot{n}]_2=\fall{100001}{2}$ and $[\ddot{n}]_2=\fall{10001}{2}$. We have $u_{16} (CF(n+1))= u_{16}(CF(\dot{n}+1))=0$ but $u_{16}(CF(\ddot{n}+1))=2$. Using $\ddot{n}$ will cause an error in enumerating $u_{16}(CF_2(c_n))$. Following the idea in the last paragraph, we will claim another important and useful theorem. Given $n\in \bbN$, let $\bar{n}$ be the integer such that $[\bar{n}]_2$ is obtained by the following rules. \ben \item[a.] When the rightmost run of $0$ in $[n]_2$ is of length $\ge k+1$, let us truncate it to be length $k$, otherwise keep it the same. \item[b.] For any other run of $0$ or $1$ of $[n]_2$ with length $\ge k$, truncate them to be length $k-1$. \een Suppose $[n]_2$ is interpreted as its two principal segments $[2\al]_2$ and $\fall{1^\be}{2}$ defined in~\ree{e_n_form_cn}. Interestingly, the corresponding two segments of $[\bar{n}]_2$ are exactly $[2\ddot{\al}]$ and $\fall{1^{\be'}}{2}$, where $\be'=\min\{\be,k-1\}$. Moreover, we have \beq \label{e_bar2n} u_q(CF_2((2n)!)) \equiv_{q/4} u_q(CF_2(\bar{2n}!)) \equiv_{q/4} u_q(CF_2((2\bar{n})!)). \eeq The second equivalence is a little bit complicated and takes time to understand. It is better to refer to the last remark. \bth \label{t_cn_bar_n} Let $n,k\in \bbN$ with $k\ge 3$ and $\al=(CF_2(n+1)-1)/2$. We have $$ c_n \equiv_{2^k} \left\{ \barr{ll} c_{\bar{n}} & \text{for $d(\al)\le k -1$, and}\\ 0 & \text{for $d(\al)\ge k$.} \earr \right. $$ \eth \pf By Theorem~\ref{t_cn_mod_q_1}, $c_n \equiv_{2^k} (-1)^{zr(\al)} 2^{d(\al)} 5^{u_q(CF_2(c_n))}$; so the condition for $c_n \equiv_{2^k} 0$ is trivial. Considering $d(\al)\le k -1$ and using the fact that $c_{\bar{n}} \equiv_{2^k} (-1)^{zr(\ddot{\al})} 2^{d(\ddot{\al})} 5^{u_q(CF_2(c_{\bar{n}}))}$. we obtain that $d(\al)=d(\ddot{\al})$ and $zr(\al)=zr(\ddot{\al})$. The proof immediately follows, after we derive \beaa u_q(CF_2(c_n)) &=\hs{6.7mm}& u_q(CF_2((2n)!))- u_q(CF_2(n+1)) -2\,u_q(CF_2(n!))\nonumber \\ &\equiv_{q/4}& u_q(CF_2((2\bar{n})!))- u_q(CF_2(2\al+1)) -2\,u_q(CF_2(\bar{n}!))\nonumber\\ &\equiv_{q/4}& u_q(CF_2((2\bar{n})!))- u_q(CF_2(2\ddot{\al}+1)) -2\,u_q(CF_2(\bar{n}!))\nonumber\\ &=\hs{6.7mm}& u_q(CF_2(c_{\bar{n}})). \nonumber \rlap{\hs{8.5cm}\Qed} \eeaa \noindent{\bf Remark.}\quad The reason for the rightmost run of $0$ banned on truncating into length $k-1$ is due to the enumeration of $u_{q}(CF_2(n+1))$. Does every number in $[0,2^k-1]$ admit to be a congruence of $c_n$ (mod $2^k$)? Theorem~\ref{t_cn_bar_n} supports a negative answer as follows. \bth \label{t_con_cn_upb} Let $k\ge 2$ and $q=2^k$. (a) If there exists $\delta\in [0,k-1]$ such that $k^{\delta+1}<2^{k-\delta-1}$, then there exists $N \in[0,q-1]$ with $\om(N)=\delta$ such that $c_n\not\equiv_q N$ for any $n$. (b) The set of congruence numbers $c_n$ (mod $q$) is a proper subset of $[0,q-1]$, and the cardinality of this set is bounded by $1+\sum_{\delta=0}^{k-1} \min(k^{\delta+1},2^{k-\delta-1})$. \eth \pf To prove part (a), we need to find a upper bound for the cardinality of $\{[\bar{n}]_2\mid \text{$n\in\bbN$ with $\omega_2(c_n)=\delta$}\}$. As usual, we split $[n]_2$ into two principal segments, $[2\al]_2$ and $\fall{1^\be}{2}$. We are provided by $d(\al)=\omega_2(c_n)=\delta\le k-1$. In the same way, $[\bar{n}]_2$ has its own principal segments, which must be $[2\ddot{\al}]$ and $\fall{1^{\be'}}{2}$ with $d(\ddot{\al})=\de$ and $\be'=\min\{\be,k-1\}$. The last two identities suggest the possible types of $[\bar{n}]_2$. There are $k^\delta$ possible $\ddot{\al}$, and $k$ possible $\be'$; so we have $k^{\delta+1}$ possible $\bar{n}$. On the other hand, there are at most $2^{k-\delta-1}$ possible congruences to match these $c_n$ (mod $q$). Therefore, the first assertion follows. Now we prove part (b). As $k=2$, we already know $c_n\not\equiv_{4} 3$. For $k\ge 3$, jut let $\delta=0$ and then $k^{\delta+1}=k<2^{k-1}$ is always true. The bound for the cardinality is a direct result from part (a). \Qed This property appeared in Theorem~\ref{t_ELY_Cat8a} as $(k,\delta)=(3,0)$. It will appear again in Theorem~\ref{t_Cat_mod16} as $(k,\delta)=(4,0)$ and in Theorem~\ref{t_Cat_mod32e} as $(k,\delta)=(6,0)$. However, in Theorem~\ref{t_Cat_mod32d} we have $k^{\delta+1}>2^{k-\delta-1}$ provided by $(k,\delta)=(6,1)$, but some congruence numbers are still missing. Using~\ree{e_bar2n} and also plugging $\bar{n}$ into~\ree{e_u16_nfac} instead of $\dot{n}$, we derive that \beaa u_{16}(CF_2(c_n)) &\equiv_4& u_{16}(CF_2((2\bar{n})!))-2u_{16}(CF_2(\bar{n}!))- u_{16}(CF_2(\bar{n}+1)) \label{e_u16_cn}\\ &\equiv_4& 2\big[c_{_2}(\bar{n})+\bar{n}_0+\bar{n}_2+ \bar{n}_0\bar{n}_2 + \#(\cS_4(\bar{n}),\{\fall{0011}{2},\fall{1\text{x}00}{2}\}) \big] \nonumber\\ &&\quad - r_1(\bar{n})- r(\bar{n}) -zr_1(\bar{n})+ zr(\bar{n})-\bar{n}_1+ \bar{n}_0\bar{n}_1 - u_{16}(CF_2(2\ddot{\al}+1)) \nonumber\\ &\equiv_4& 2\big[ c_{_2}(\bar{n})+ (1-\bar{n}_0)(1-\bar{n}_2) + \#(\cS_4(\bar{n}), \{\fall{0011}{2},\fall{1\text{x}00}{2}\}) \big] \nonumber\\ &&\quad +1- r_1(\bar{n})-zr_1(\bar{n})+(1-\bar{n}_0)(1-\bar{n}_1) - [\ddot{\al}_0+\ddot{\al}_1+2\ddot{\al}_2-2\ddot{\al}_0\ddot{\al}_1] \label{e_u16cn1}\\ &\equiv_4& \chi(\be'=0)(2\ddot{\al}_1-\ddot{\al}_0-1)-\chi(\be'=1)+2\chi(\be'=2)\ddot{\al}_0+ 2\chi(\be'=3)(1-\ddot{\al}_0)\nonumber\\ &&\quad +2\big[c_{_2}(\ddot{\al})+\ddot{\al}_0(1-\ddot{\al}_2)+\#(\cS_4(\ddot{\al}),\{\fall{0011}{2}, \fall{1\text{x}00}{2}\}) \big] -r_1(\ddot{\al})\nonumber\\ &&\quad -zr_1(\ddot{\al})+\ddot{\al}_0\ddot{\al}_1+1. \label{e_u16cn2} \eeaa To derive~\ree{e_u16cn1}, we need the identity $r(\bar{n})-zr(\bar{n})=\bar{n}_0$ and refer to~\ree{e_u8t}. With the help of~\ree{e_u16cn2}, we can turn $d(\al)=k-3$ to be a solved case for the problem of $c_n$ (mod $q$). \bco \label{c_cn_eq16} Let $n,k\in \bbN$, $\al= (CF_2(n+1)-1)/{2}$ and $k-d(\al)= 3$. Then we have \beq c_n \equiv_q (-1)^{zr(\al)}\big[ 2^{k-3} + 2^{k-1} u_{16}(CF_2(c_n)) \big]. \eeq \eco \pf Let us apply Theorem~\ref{t_cn_mod_q_1} and derive that \bea c_n &\equiv_q& (-1)^{zr(\al)}2^{d(\al)}(1+4)^{u_q(CF_2(c_n))} \\ &\equiv_q& (-1)^{zr(\al)}2^{k-3} \big[1+ 4\,u_q(CF_2(c_n)) \big]\\ &\equiv_q& (-1)^{zr(\al)}2^{k-3} \big[1+ 4\,u_{16}(CF_2(c_n)) \big], \eea where the last equivalence is due to $u_q(t)\equiv_2 u_{16}(t)$, a result of Lemma~\ref{l_uq_uq}. \Qed Finally, we state and prove our main result of this section. \bth \label{t_Cat_mod16} Let $c_n$ be the $n$-th Catalan number. First of all, $c_n \not\equiv_{16} 3,7,9,11,15$ for any $n$. As for the other congruences, we have \begin{equation*} c_n \equiv_{16} \left\{ \barr{l@{\quad\text{if}\quad}l} \left. \barr{r} 1\\ 5\\ 13 \earr \right\} & \textit{$d(\al)=0$ and \quad} \left\{ \barr{l} \be\le 1,\\ \be=2,\\ \be\ge 3, \earr \right. \\ \left. \barr{r} 2\\ 10 \earr \right\} & \textit{$d(\al)=1$, $\al=1$ and \quad} \left\{ \barr{l} \be=0 \text{ or } \be\ge 2,\\ \be=1,\earr \right. \\ \left. \barr{r} 6\\ 14 \earr \right\} & \textit{$d(\al)=1$, $\al\ge2$ and \quad} \left\{ \barr{l} (\al=2,\be\ge 2) \text{ or } (\al\ge 3,\be\le 1),\\ (\al=2,\be\le 1) \text{ or } (\al\ge 3,\be\ge 2), \earr \right. \\ \left. \barr{r} 4\\ 12 \earr \right\} & \textit{$d(\al)=2$ and \quad} \left\{ \barr{l} zr(\al)\equiv_2 0,\\ zr(\al)=1, \earr \right. \\ \left. \barr{r}\ \, 8 \earr \right. & \textit{$d(\al)=3$,}\\ \left. \barr{r}\ \, 0 \earr \right. & \textit{$d(\al)\ge 4$.} \earr \right. \end{equation*} where $\al= (CF_2(n+1)-1)/2$ and $\be= \omega_2(n+1)$ (or $\be=\min\{i\mid n_i=0\}$). \eth \pf Congruences $0,4,8$ and $12$ are trivial cases. Suppose $d(\al)=1$ (so $\al\ge 1$). Here $b(CF_2(c_n))=zr(\al)$ can only be $0$ or $1$ depending on $\al=1$ or $\al\ge 2$ respectively. Moreover, $u_8(CF_2(c_n))\equiv_2 \chi(\al=2)+ \chi(\be=1)+ \chi(\al\ge 2)\chi(\be\ge 1)$ by~\ree{e_u8cn}. Let us use the following table of $(b(CF_2(c_n)), u_8(CF_2(c_n)))$ for discussion. $$ \begin{tabular}{c|ccc} & $\al=1$ & $\al=2$ & $\al\ge 3$ \\ \hline $\be=0$& (0,0) & (1,1) & (1,0) \\ $\be=1$& (0,1) & (1,1) & (1,0) \\ $\be\ge 2$& (0,0) & (1,0) & (1,1) \\ \end{tabular} $$ We conclude the congruences $2,6,10,14$ by using this table and referring to the isomorphism $Z^\ast_8\cong C_2\times C_2$ in Table~\ref{tab_iso}. For instance, if $(\al,\be)=(2,1)$ then $(b(CF_2(c_n)), u_8(CF_2(c_n)))=(1,1)$. Hence $CF_2(c_n)\equiv_8 7$ and then $c_n\equiv_{16} 2\times 7=14$. For $d(\al)=k-3$, we can also use Lemma~\ref{c_cn_eq16} to obtain the same result. Now suppose $d(\al)=0$. Clearly, $\al=0$ and $b(CF_2(c_n))=zr(\al)=0$. Let us adopt a new notation $\bar{n}$ such that $[2\ddot{\al}]_2$ and $\fall{1^{\be'}}{2}$ are the principal segments of $[\bar{n}]_2$. Notice that $\be'=\min\{\be,3\}$. Since $\ddot{\al}=0$ (due to $\al=0$), every term involving $\ddot{\al}$ in~\ree{e_u16cn2} turns to $0$. Thus, we have $u_{16}(CF_2(c_n))=-\chi(\be'=0)-\chi(\be'=1)+2\chi(\be'=3)+1$, which equals $0,0,1,3$ if $\be'=0,1,2,3$ respectively. The congruences $1,5,13$ are done by case-discussion and referring to Table~\ref{tab_iso}. \Qed The lack of congruences $3,7,11,15$ with respect to modulus $16$ is inherited from the lack of $3,7$ with respect to modulus $8$ in Theorem~\ref{t_ELY_Cat8}, but the lack of $9$ is a new result. \section{$u_{32}(CF_2(n!))$ and $u_{64}(CF_2(n!))$; $c_n\pmod{64}$} \label{s_u32_u64_cm64} First, let us show the easy cases without proof: $c_n\equiv_{64} 0, 16. 32$ or $48$, as provided by $d(\al)\ge 4$. \bth \label{t_Cat_mod32a} Given $n\in \bbN$ with $\al=(CF_2(n+1)-1)/2$, we have \begin{equation*} c_n \equiv_{64} \left\{ \barr{r@{\quad\text{if}\quad}l} \left. \barr{r} 16\\ 48 \earr \right\} & \textit{$d(\al)=4$ and \quad} \left\{\barr{l} zr(\al)\equiv_2 0 \\ zr(\al)\equiv_2 1, \earr \right. \\ 32 \hs{5.5mm} & d(\al)=5,\\ 0 \hs{5.5mm} & d(\al)\ge 6. \earr \right. \end{equation*} \eth The next class is for $c_n\equiv_{64} 8, 24, 40$ or $56$. \bth \label{t_Cat_mod32b} Given $n\in \bbN$ with $d(\al)=3$, we suppose $[\al]_2=\fall{10^a10^{b}10^c}{2}$, i.e., $[n]_2=\fall{10^a10^b1 0^{c+1} 1^\be}{2}$. Also we define \bea B&:=& \chi(a\ge 1) + \chi(b\ge 1) + \chi(c\ge 1) \textit{ and}\\ U&:=& \chi(a=1) + \chi(b=1) + \chi(c=1) + \chi(b\ge 1)[\chi(a\ge 1) + \chi(c=0)] +\chi(\be\ge 2) +1. \eea Then we have \begin{equation*} c_n \equiv_{64} \left\{ \barr{r@{\quad\text{if}\quad}l@{\quad\text{and}\quad}l} 8 & B\equiv_2 0 & U\equiv_2 0,\\ 24 & B\equiv_2 1 & U\equiv_2 0,\\ 40 & B\equiv_2 0 & U\equiv_2 1,\\ 56 & B\equiv_2 1 & U\equiv_2 1. \earr \right. \end{equation*} or simply $$ c_n \equiv_{64} 8 \times [4 \chi(U\equiv_2 1) +2 \chi(B\equiv_2 1) +1]. $$ \eth \pf Because $d(\al)=3$ we have $\omega_2(c_n)=3$ and $CF_2(c_n)=1,3,5,7$. To determine the value of $CF_2(c_n)$ we shall refer to $T_8(CF_2(c_n))$. Now use \ree{e_bCF_cn} and \ree{e_u8cn} to interpret $T_8(CF_2(c_n))$ as follows: $$ b(CF_2(c_n))\equiv_2 zr(\al) = \chi(a\ge 1) + \chi(b\ge 1) + \chi(c\ge 1), $$ which is $B$, and \bea u_8(CF_2(c_n)) &\equiv_2& \chi(\be\ge 2)+\chi(\al=1,\be=0) +r(\al) +r_1(\al) +zr_1(\al) +\al_0(1- \al_1)\\ &=& \chi(\be\ge 2) + 0 +[1+\chi(a\ge 1)+\chi(b\ge 1)]+[\chi(a\ge 1)+\chi(b\ge 1)\\ & & \quad +\chi(a\ge 1)\chi(b\ge 1)] +[\chi(a= 1) + \chi(b= 1)+\chi(c= 1)]\\ & & \quad + \chi(b\ge 1,c=0), \eea which is $U$ after simplifying. \Qed For those $c_n$ (mod $64$) with $\omega_2(c_n)=2$, we can simply plug $u_{16}(c_n)$ given in~\ree{e_u16cn2} into~\ree{e_cn_mod_q_1}. Here we also show a precise classification by tables. \bth \label{t_Cat_mod32c} Let $n\in \bbN$ with $d(\al)=2$. Then we have $$ c_n \equiv_{64} (-1)^{zr(\al)} 4\times 5^{u_{16}(CF_2(c_n))}, $$ where $u_{16}(CF_2(c_n))$ is given in \ree{e_u16cn2}. Precisely, let $[\al]_2=\fall{10^a1 0^{b}}{2}$, i.e., $[n]_2=\fall{10^a1 0^{b+1} 1^\be}{2}$, and then we have $c_n$ (mod $64$) shown in the following four tables. $$ \btab{c|cccc} & $a=0$ & $a=1$ & $a=2$ & $a\ge 3$ \\ \hline $b=0$& $ 4$& $28$& $44$& $12$\\ $b=1$& $12$& $36$& $52$& $20$\\ $b=2$& $60$& $20$& $36$& $ 4$\\ $b\ge 3$& $28$& $52$& $ 4$& $36$\\[1mm] \multicolumn{5}{c}{when $\be=0$} \etab \qquad \btab{c|cccc} & $a=0$ & $a=1$ & $a=2$ & $a\ge 3$ \\ \hline $b=0$& $52$& $12$& $28$& $60$\\ $b=1$& $44$& $ 4$& $20$& $52$\\ $b=2$& $60$& $20$& $36$& $ 4$\\ $b\ge 3$& $28$& $52$& $ 4$& $36$\\[1mm] \multicolumn{5}{c}{when $\be=1$} \etab $$ $$ \btab{c|cccc} & $a=0$ & $a=1$ & $a=2$ & $a\ge 3$ \\ \hline $b=0$& $36$& $28$& $44$& $12$\\ $b=1$& $28$& $20$& $36$& $ 4$\\ $b=2$& $44$& $36$& $52$& $20$\\ $b\ge 3$& $12$& $ 4$& $20$& $52$\\[1mm] \multicolumn{5}{c}{when $\be=2$} \etab \qquad \btab{c|cccc} & $a=0$ & $a=1$ & $a=2$ & $a\ge 3$ \\ \hline $b=0$& $ 4$& $60$& $12$& $44$\\ $b=1$& $60$& $52$& $ 4$& $36$\\ $b=2$& $12$& $ 4$& $20$& $52$\\ $b\ge 3$& $44$& $36$& $52$& $20$\\[1mm] \multicolumn{5}{c}{when $\be\ge 3$} \etab $$ \eth \pf Notice that there are difference between $a\ge 3$ and $a=3$, and similarly for $b$ and $\be$. We split~\ree{e_u16cn2} into two parts as follows: \bea A &:=& \chi(\be'=0)(2\ddot{\al}_1-\ddot{\al}_0-1)-\chi(\be'=1)+2\chi(\be'=2)\ddot{\al}_0+ 2\chi(\be'=3)(1-\ddot{\al}_0),\\ B &:=& 2\big[c_{_2}(\ddot{\al})+\ddot{\al}_0(1-\ddot{\al}_2)+\#(\cS_4(\ddot{\al}),\{\fall{0011}{2}, \fall{1\text{x}00}{2}\}) \big] -r_1(\ddot{\al})-zr_1(\ddot{\al})\\ &&\quad +\ddot{\al}_0\ddot{\al}_1+1. \eea Clearly, $B$ is independent on $\be'$. We will only prove the first table of this theorem. The other three tables can be checked in the same way. With simple calculation we obtain the values of $A$ as $\be=0$ and $B$ as follows: $$ \btab{c|cccc} & $a=0$ & $a=1$ & $a=2$ & $a= 3$ \\ \hline $b=0$& $0$& $2$& $2$& $2$\\ $b=1$& $1$& $1$& $1$& $1$\\ $b=2$& $3$& $3$& $3$& $3$\\ $b=3$& $3$& $3$& $3$& $3$\\[1mm] \multicolumn{5}{c}{value of $A$ when $\be=0$} \etab \qquad \btab{c|cccc} & $a=0$ & $a=1$ & $a=2$ & $a= 3$ \\ \hline $b=0$& $0$& $2$& $1$& $3$\\ $b=1$& $0$& $1$& $2$& $0$\\ $b=2$& $3$& $2$& $3$& $1$\\ $b=3$& $1$& $0$& $1$& $3$\\[1mm] \multicolumn{5}{c}{value of $B$} \etab $$ These two tables contribute $u$. Since we also know $b(CF_2(c_n))\equiv_2 zr(\al)=\chi(a\ge 1)+\chi(b\ge 1)$, we obtain $(b,u)$ as follows: $$ \btab{c|cccc} & $a=0$ & $a=1$ & $a=2$ & $a=3$ \\ \hline $b=0$& $(0,0)$& $(1,0)$& $(1,3)$& $(1,1)$\\ $b=1$& $(1,1)$& $(0,2)$& $(0,3)$& $(0,1)$\\ $b=2$& $(1,2)$& $(0,1)$& $(0,2)$& $(0,0)$\\ $b=3$& $(1,0)$& $(0,3)$& $(0,0)$& $(0,2)$\\ \etab $$ Now refer to the isomorphism $\bbZ_{16}^\ast \cong C_2\times C_{4}$ in Table~\ref{tab_iso} to obtain the corresponding numbers, and then multiply each of them by $4$ to justify the first table of this theorem. \Qed \noindent {\bf Remark.}\quad No congruence is missing in the previous two theorems. But, in the remaining two classes in the following, some congruences will never been achieved, just like $c_4\not\equiv_4 3$. To settle down the remaining congruences of $c_n$ (mod $64$), we need to further deal with $u_{32}(CF_2(n!))$ and $u_{64}(CF_2(n!))$. Let us mimic the last section by using the isomorphism $\bbZ_{32}^\ast \cong C_2\times C_{8}$ in Table~\ref{tab_iso} as follows: $$ \begin{tabular}{c|ccccccccccccccc} $t\in \bbZ_{32}^\ast$ & 3 & 5 & 7 & 9 &11 &13 &15 &17 &19 &21 &23 &25 &27 &29 &31\\ \hline $u_{32}(t)\in C_{8}$ & 7 & 1 & 6 & 6 & 1 & 7 & 0 & 4 & 3 & 5 & 2 & 2 & 5 & 3 & 4\\ $\sum_{s\in [3,t]_{\text{o}}} u_{32}(s)\hs{-2.3mm} \pmod{8}$ & 7 & 0 & 6 & 4 & 5 & 4 & 4 & 0 & 3 & 0 & 2 & 4 & 1 & 4 & 0 \end{tabular} $$ So we have \beaa u_{32}(CF_2(n!)) &\equiv_8& \#(\cS_5(\ddot{n}),\{3^7,4^7,7^6,8^6,9^4,10^4,11^5,12^5, 13^4,14^4,15^4,16^4,19^3,20^3, \nonumber\\ &&\qquad 23^2,24^2,25^4,26^4,27,28,29^4,30^4\}) \label{e_u32_fac}\\ &=:&\phi_{32}(\cS_5(\ddot{n})). \nonumber \eeaa In this formula, $\ddot{n}$ can be replaced by $n$, $\dot{n}$ or $\bar{n}$. Unlike our operation from~\ree{e_u16_nfac1} to~\ree{e_u16_nfac}, we are not going to simplify this formula, because it is good enough to deal with $c_n$ (mod $64$); nevertheless, it would be worth developing a simpler form in the future. Above, we also define $\phi_{32}(\cS_5(\ddot{n}))$ to be the right hand side of~\ree{e_u32_fac}, in order to plug into $\phi_{32}$ with some other multi-sets instead of $\cS_5(\ddot{n})$. In the following, we set $\phi_{32}(\{[t]_2\}):= \phi_{32}(\{t\})$ for convenience. \beaa u_{32}(CF_2(c_n)) &\equiv_8& \phi_{32}(\cS_5(2\ddot{n})) -2\phi_{32}(\cS_5(\ddot{n})) -u_{32}(CF_2(\bar{n}+1)) \nonumber\\ &\equiv_8& \phi_{32}(\{\fall{\ddot{n}_3\ddot{n}_2\ddot{n}_1\ddot{n}_0 0}{2}\}) -\phi_{32}(\cS_5(\ddot{n})) -u_{32}(\fall{\ddot{\al}_3\ddot{\al}_2\ddot{\al}_1\ddot{\al}_0 1}{2}). \label{e_u32_cn} \eeaa By this formula, we can classify $c_n$ (mod $64$) for those $n$ with $d(\al)=1$ as follows: \bth \label{t_Cat_mod32d} Let $n\in \bbN$ with $d(\al)=1$. The congruences of $c_n$ (mod $64$) are classified by the following table. $$ \btab{c|ccccc} & $\al=1$ & $\al=2$ & $\al=2^2$ & $\al=2^3$ & $\al=2^s$ \\ \hline $\be=0$& $2 $& $14$& $22$& $38$& $6 $\\ $\be=1$& $42$& $62$& $54$& $38$& $6 $\\ $\be=2$& $34$& $22$& $14$& $62$& $30$\\ $\be=3$& $18$& $6 $& $62$& $46$& $14$\\ $\be\ge 4$&$50$&$38$&$30$& $14$& $46$ \etab $$ where $s\ge 4$. \eth \pf Adopt $[\ddot{\al}]_2$ and $\fall{1^{\be'}}{2}$ as the two principal segments of $[\bar{n}]_2$ for $k=5$ (not $6$). We shall have $d(\ddot{\al})=d(\al)=1$ and $\be'=\min\{\be, 5\}$. We use~\ree{e_bCF_cn} and~\ree{e_u32_cn} to obtain the next table for $(b(CF_2(c_n)), u_{32}(CF_2(c_n)))$ as follows: $$ \btab{c|ccccc} & $\ddot{\al}=1$ & $\ddot{\al}=2$ & $\ddot{\al}=2^2$ & $\ddot{\al}=2^3$ & $\ddot{\al}=2^4$\\ \hline $\be'=0$& $(0,0) $& $(1,6) $& $(1,1) $& $(1,3) $& $(1,7) $\\ $\be'=1$& $(0,5) $& $(1,4) $& $(1,5) $& $(1,3) $& $(1,7) $\\ $\be'=2$& $(0,4) $& $(1,1) $& $(1,6) $& $(1,4) $& $(1,0) $\\ $\be'=3$& $(0,6) $& $(1,7) $& $(1,4) $& $(1,2) $& $(1,6) $\\ $\be'=4$& $(0,2) $& $(1,3) $& $(1,0) $& $(1,6) $& $(1,2) $ \etab $$ Now find every corresponding number by referring to the isomorphism $\bbZ_{32}^\ast \cong C_2\times C_{16}$ in Table~\ref{tab_iso}, and then multiply the number by $2$ to obtain the table in this theorem. \Qed \bco We have $c_n \not\equiv_{64} 10,26$ and $58$. \eco The final class will be solved after we realize $u_{64}(CF_2(c_n))$. Here we skip some detail, especially a huge table for the sum $\sum_{t\in [3,s]_{\text{o}}} u_{64}(s)$ (mod $16$). We show the formulae of $u_{64}(CF_2(n!))$ and $u_{64}(CF_2(c_n))$ directly as follows: \beaa u_{64}(CF_2(n!)) &\equiv_{16}& \#(\cS_6(\ddot{n}),\{3^{11},4^{11},5^{12},6^{12},7^{14}, 8^{14},9^{4},10^{4},11,12,15^{12},16^{12},17^{8},18^{8}, \nonumber\\ &&\qquad 19^{7},20^{7},21^{4},22^{4},23^{10},24^{10},25^{12},26^{12},27^{13},28^{13} 29^{8},30^{8},31^{8},32^{8}, \nonumber\\ &&\qquad 35^{3},36^{3},37^{12},38^{12},39^{6},40^{6},41^{4},42^{4},43^{9}, 44^{9},47^{4},48^{4},49^{8},50^{8},\nonumber\\ &&\qquad 51^{15},52^{15},53^{4},54^{4},55^{2},56^{2},57^{12},58^{12}, 59^{5},60^{5},61^{8},62^{8}\}) \label{e_CF64n}\\ &=:&\phi_{64}(\cS_6(\ddot{n})); \nonumber\\ u_{64}(CF_2(c_n)) &\equiv_{16}& \phi_{64}(\cS_6(2\ddot{n})) -2\phi_{64}(\cS_6(\ddot{n})) -u_{64}(CF_2(\bar{n}+1)) \nonumber\\ &\equiv_{16}& \phi_{64}(\{\fall{\ddot{n}_4\ddot{n}_3\ddot{n}_2\ddot{n}_1\ddot{n}_0 0}{2}\}) -\phi_{64}(\cS_6(\ddot{n})) -u_{64}(\fall{\ddot{\al}_4\ddot{\al}_3\ddot{\al}_2\ddot{\al}_1\ddot{\al}_0 1}{2}). \label{e_u64_cn} \eeaa The following theorem is directly checked by~\ree{e_u64_cn}; so we skip its proof. On the other hand, by Theorem~\ref{t_cn_bar_n}, we can verify this theorem by only enumerating $c_0,c_1,c_3,c_7,c_{15}$, and $c_{31}$ (mod $64$). \bth \label{t_Cat_mod32e} Let $n\in \bbN$ with $d(\al)=0$, i.e. $n=2^\be-1$. Then we have $$ c_n \equiv_{64} \left\{ \barr{r@{\quad \text{if}\quad}l} 1 & \be=0 \text{ or } 1;\\ 5 & \be=2;\\ 45& \be=3;\\ 61& \be=4;\\ 29& \be\ge 5.\\ \earr \right. $$ Moreover, any number in $[0,63]_{\rm o}-\{1,5,29,45,61\}$ can never be the congruence of $c_n$ (mod $64$). \eth \section{Future research and acknowledgements} \label{s_FR_A} The odd congruences of $c_n$ (mod $2^k$) happen if and only if $n=2^{m}-1$ for $m\in\bbN$. After observing all odd congruences from modulus $4$ up to modulus $1024$, once we conjectured the following property. It was soon proved by H.-Y. Lin~\cite{Lin_2010}. \bth Let $k\ge 2$. There only exist $k-1$ different odd congruences $c_n$ (mod $2^k$), and they are $c_{2^{m}-1}$ (mod $2^k$) for $m=1,2,\ldots,k-1$. \eth In other words, if $n= 2^m-1$ then $c_n$ (mod $2^k$) are distinct odd integers for $m=1,2,\ldots,k-1$. Associated with this theorem, there are a trivial fact $c_0 \equiv_{2^k} c_1 \equiv_{2^k} 1$ and a non-trivial fact $c_{2^{m}-1} \equiv_{2^k} c_{2^{k-1}-1}$ for each $m\ge k$ that directly follows Theorem~\ref{t_cn_bar_n}. The final interest is to develop a systematic algorithm for calculating the modularity of various combinatorial numbers. But that is a long-term goal. So far some further research directions in our mind are \ben \item[(a)] The congruences of $c_n$ (mod $p^k$) for some odd prime $p$, which is a continuation of the work of this paper; \item[(b)] The congruences of some other combinatorial numbers modulo a prime power, in particular, $\binom{m}{n}$ and Motzkin numbers; \item[(c)] A more efficient isomorphic machine exchanging between $\bbZ_{q^k}^\ast$ and the corresponding additive group, in order to facilitate the arguments of this paper; \item[(d)] In case that part (c) is admissible for some higher power of a prime, we hope to derive an algorithm to enumerate congruences for various combinatorial numbers. \een The second author thanks the Institute of Mathematics at the Academia Sinica for stimulating this joint work when she participated in the Summer School for Undergraduate Research held there. Both authors would like to thank Prof.\ Peter Shiue, Prof.\ Bruce Sagan and the anonymous referees for many comments and suggestions for improving the original version of this paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \vspace{1cm} \baselineskip=16pt \begin{thebibliography}{99} \bibi{Alter_Kubota_73} R. Alter and K. K. Kubota, Prime and prime power divisibility of Catalan numbers, {\it J. Combin.\ Theory Ser.\ A} {\bf 15} (1973), 243--256. \bibi{Davis_Webb_90} K. S. Davis and W. A. Webb, Lucas' theorem for prime powers, {\it \ejc} {\bf 11} (1990), 229--233. \bibi{Davis_Webb_91} K. S. Davis and W. A. Webb, Pascal's triangle modulo 4, {\it Fibonacci Quart.}{} {\bf 29} (1991), 79--83. \bibi{Deutsch_Sagan_06} E. Deutsch and B. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, {\it J. Number Theory} {\bf 117} (2006), 191--215. \bibi{Dickson_19} L. E. Dickson, {\it History of the Theory of Numbers}, Vol. I, Chelsea, 1919 (Chapter XI). \bibi{Donaghey_Shapiro_77} R. Donaghey and L. W. Shapiro, Motzkin Numbers, {\it J. Combin.\ Theory Ser.\ A} {\bf 23} (1977), 291--301. \bibi{Eu_Liu_Yeh_06} S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, On the congruences of some combinatorial numbers, {\it Stud.\ Appl.\ Math.} {\bf 116} (2006), 135--144. \bibi{Eu_Liu_Yeh_07} S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, Catalan and Motzkin numbers modulo $4$ and $8$, {\it\ejc} {\bf 29} (2008), 1449--1466. \bibi{Fine_02} N. J. Fine, Binomial coefficients modulo a prime, {\it Amer.\ Math.\ Monthly} {\bf 54} (1947), 589--592. \bibi{Gessel_82} I. M. Gessel, Some congruences for Ap\'{e}ry numbers, {\it J. Number Theory} {\bf 14} (1982), 362--368. \bibi{Granville} A. Granville, Arithmetic properties of binomial coefficients I: binomial coefficients modulo prime powers, available at \\ \href{http://www.cecm.sfu.ca/organics/papers/granville/index.html}{\tt http://www.cecm.sfu.ca/organics/papers/granville/index.html} . \bibi{Granville_92} A. Granville, Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's Triangle, {\it Amer.\ Math.\ Monthly} {\bf 99} (1992), 318--381. \bibi{Huard_Spearman_Williams_98} J. G. Huard, B. K. Spearman, and K. S. Williams, Pascal's triangle (mod 8), {\it\ejc} {\bf 19} (1998), 45--62. \bibi{Kummer_852}E. E. Kummer, \"{U}ber die Erg\"{a}nzungss\"{a}tze zu den allgemeinen Reciprocit\"{a}tsgesetzen, {\it J. Reine Angew.\ Math.}{} {\bf 44} (1852), 93--146. \bibi{Lin_2010} H.-Y. Lin, Odd Catalan numbers modulo $2^k$, to appear in {\it\ejc} \bibi{Luca_Klazar_05} F. Luca and M. Klazar, On integrality and periodicity of the Motzkin numbers, {\it Aequ.\ Math.}{} {\bf 69} (2005), 68--75. \bibi{Lucas_877} E. Lucas, Sur les congruences des nombres eul\'eriens et des coefficients diff\'erentiels des fonctions trigonom\'etriques suivant un module premier, {\it Bull.\ Soc.\ Math.\ France} {\bf 6} (1878), 49--54. \bibi{Mimura_83} Y. Mimura, Congruence properties of Apery numbers, {\it J. Number Theory} {\bf 16} (1983), 138--146. \bibi{Rost_Sagan_94} A. Postnikov and B. Sagan, Note: What power of two divides a weighted Catalan number, {\it\jcta} {\bf 114} (2007), 970--977. \bibi{Riesel_94} H. Riesel, {\it Prime Numbers and Computer Methods for Factorization}, Springer, 1994. \bibi{Stanley_99} R. P. Stanley, {\it Enumerative Combinatorics}, Vol.\ 2, Cambridge University Press, 1999. \bibi{Wolfram_02} S. Wolfram, {\it A New Kind of Science}, Wolfram Media, 2002. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A10; Secondary 11B50. \noindent \emph{Keywords: } prime power modulus, Catalan numbers, Kummer's theorem, Lucas' theorem. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 14 2010; revised version received April 30 2010. Published in {\it Journal of Integer Sequences}, May 3 2010. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}