Catalan Numbers Modulo 2^{k}

Shu-Chung Liu^{1} Department of Applied Mathematics National Hsinchu University of Education Hsinchu, Taiwan

              liularry@mail.nhcue.edu.tw

and

Jean C.-C. Yeh Department of Mathematics Texas A & M University College Station, TX 77843-3368 USA

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} ≡_{2^{k}} cn̄ is derived, where 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 ≥ 2.

1 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 [22]). As a pioneer in this problem, Kummer formulated the maximum power of p dividing \binom{n}{k} [14, see also Theorem 2.4]. Lucas, another early researcher, developed the very useful calculating formula \binom{n}{k} ≡_{p} ∏_{i} \binom{n_{i}}{r_{i}}, where “≡_{p}” denotes the equivalence of congruence modulo p; and each n_{i} (similarly for each r_{i}) is obtained from [n]_{p} := ⟨n_{s} ⋯ n_{1}n_{0}⟩_{p} denoting the sequence of digits representing n in the base-p system [17, or see Theorem 2.5]. A generalization of Lucas’ Theorem for a prime power was established by Davis and Webb [2]. The classical problem of Pascal’s triangle also has versions for modulus 4 and modulus 8 [3, 13]. The behavior of Pascal’s triangle modulo higher powers of p is more complicated. Some rules of the behavior are discussed by Granville [12]. The reader can also refer to [11] for a survey of binomial coefficients modulo prime powers.

1Partially supported by NSC96-2115-M-134-003-MY2

Several other combinatorial numbers have been studied for their congruences, for example, Apéry numbers [10, 18], Central Delannoy numbers [7] and weighted Catalan numbers [19].

The p-adic order of a positive integer n is denoted and defined as

ω_{p}(n) := max{α ∈ ℕ : p^{α}|n}.

We also use p^{α}∥n to denote the property that p^{α}|n but p^{α+1}|/n. The cofactor of n with respect to p^{ω_{p}(n)}, which is denoted and defined as

CF_{p}(n) := \frac{n}{p^{ω_{p}(n)}} ,

is an important object in this paper. We also call CF_{p}(n) the (maximal) p-free factor of n. The value ω_{p} indicates the divisibility by powers of p, which can be found in many previous studies (see for example [5]). However, the studies on CF_{p} was a little bit rare before. One of formulae about CF_{p} is that

CF_{p}(\binom{m}{n}) ≡_{p} (−1)^{ω_{p}(\binom{m}{n})} ∏_{i≥0} \frac{m_{i}!}{n_{i}!r_{i}!},  (1)

where r = m − n. This formula was found by each of Anton (1869), Stickelberger (1890) and Hensel (1902). A generalized formula of (1) for modulus p^{k} can be found in [11]. Recently, Eu, Liu and Yeh used CF_{p} to enumerate the congruences of Catalan numbers and Motzkin number modulo 4 and 8 [8]. Note that this cofactor was denoted by NF_{p}(n) in their paper.

Given a product ∏_{i=1}^{a} M_{i} of integers M_{i}, clearly ω_{p}(∏_{i=1}^{a} M_{i}) = ∑_{i=1}^{a} ω_{p}(M_{i}) and usually it is easy to calculate; but CF_{p}(∏_{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 ℤ_{q} := ℤ/qℤ, we shall narrow our attention to the modulo multiplication group ℤ_{q}^{∗} := {t ∈ ℤ_{q} | (t, q) = 1}. To evaluate CF_{p} (mod q), Eu, Liu and Yeh [8] recently introduced a new index E_{q,t}, the t-encounter function of modulus q, with respect to a product ∏_{i=1}^{a} M_{i} is denoted and defined as

E_{q,t}(∏_{i=1}^{a} M_{i}) := ∑_{i=1}^{a} χ(CF_{p}(M_{i}) ≡_{q} t),

where χ is the Boolean function. If ω_{p}(∏_{i=1}^{a} M_{i}) ≥ k, then ∏_{i=1}^{a} M_{i} ≡_{q} 0; otherwise

∏_{i=1}^{a} M_{i} ≡_{q} p^{ω_{p}(∏_{i=1}^{a} M_{i})} ∏_{t∈ℤ_{q}^{∗}} t^{E_{q,t}(∏_{i=1}^{a} M_{i})}.  (2)

The evaluation of ∏_{t∈ℤ_{q}^{∗}} t^{E_{q,t}(∏_{i=1}^{a} M_{i})} shall be operated in ℤ_{q}^{∗}. Alternatively and more efficiently,

∏_{i=1}^{a} M_{i} ≡_{q} p^{ω_{p}(∏_{i=1}^{a} M_{i})} ∏_{t∈ℤ_{q′}^{∗}} t^{E_{q′,t}(∏_{i=1}^{a} M_{i})},  (3)

where q′ = p^{k′} with some k′ such that k − ω_{p}(∏_{i=1}^{a} M_{i}) ≤ k′ ≤ k.

Many combinatorial numbers are in form of quotient ∏_{i=1}^{a} M_{i}/ ∏_{j=1}^{b} N_{j}. By analogy, let us define

E_{q,t}(\frac{∏_{i=1}^{a} M_{i}}{∏_{j=1}^{b} N_{j}}) := E_{q,t}(∏_{i=1}^{a} M_{i}) − E_{q,t}(∏_{j=1}^{b} N_{j}),

and then

\frac{∏_{i=1}^{a} M_{i}}{∏_{j=1}^{b} N_{j}} ≡_{q} p^{ω_{p}(∏_{i=1}^{a} M_{i})−ω_{p}(∏_{j=1}^{b} N_{j})} ∏_{t∈ℤ_{q}^{∗}} t^{E_{q,t}( \frac{∏{a \atop i=1} M_{i}}{∏{b \atop j=1} N_{j}})}.  (4)

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 ω_{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 [8]. Here we improve their calculating techniques and challenge higher moduli up to 64.

It is well known that ℤ_{2^{k}}^{∗} is isomorphic to C_{2} × C_{2^{k−2}} (k ≥ 2), and the group ℤ_{p^{k}}^{∗} is cyclic for any odd prime p. A breakthrough of our work is that by transforming the multiplicative group ℤ_{n}^{∗} to the corresponding additive group and fitting ∏_{t∈ℤ_{q}^{∗}} t^{E_{q,t}(∏_{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 [8] become easy applications.

We not only work for moduli 8, 16 and 64, but also develop several general properties. In Theorem 4.4, we derive that c_{n} (mod 2^{k}) is equivalent to the multiple of certain powers of 2 and 5. In Corollaries 4.3, 4.5 and 5.4, we derive three easy formulae for c_{n} (mod 2^{k}) in case that ω_{2}(c_{n}) = k − d for d = 1, 2, 3 respectively. In addition, Theorems 5.1 and 5.2 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 5.3, which claims that not every number in [0, 2^{k} − 1] admits to be a congruence of c_{n} (mod 2^{k}) for k ≥ 2.

The paper is organized as follows. In Section 2, the tools CF_{2} and E_{2^{k},t}, introduced by Eu, Liu and Yeh [8], 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 ω_{p} and E_{q,t}. An isomorphism T_{q} from the multiplicative group ℤ_{p^{k}}^{∗} to an additive group is introduced in Section 3. Some results for T_{2^{k}}(CF_{2}(n!)) and T_{2^{k}}(CF_{2}(c_{n})) are given there. In Sections 4, 5 and 6, we study the congruences of c_{n} with moduli 8 (re-proving the result in [8]), 16 and 64, respectively. Several comments for further research are given in Section 7, the final section.

2 ω_{p}(n!) and E_{q,t}(n!); Borrows and Carries

Recall the p-adic order ω_{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 ω_{p}(n!) and E_{q,t}(n!). The first lemma of this section is generalized from the two similar lemmas in [8]. Before giving that lemma, we need some new notation.

Let [a, b] := {a, a+1, …, b} for two integers a and b, where a ≤ b. Additionally, let [a, b]_{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, …, 9, we want to transform it into a base-p expansion using digits 0, 1, …, p − 1. Such an expansion is denoted as a sequence of digits

[n]_{p} := ⟨n_{r}n_{r−1} ⋯ n_{1}n_{0}⟩_{p},

provided p^{r} ≤ n < p^{r+1} for some r ∈ ℕ and n = n_{r}p^{r} + n_{r−1}p^{r−1} + ⋯ + n_{1}p + n_{0} with n_{i} ∈ [0, p − 1], where n_{i} is called the i-th place digit of [n]_{p} (or of n). For convenience, we also let n_{r+1} = n_{r+2} = ⋯ = 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

|⟨n_{r}n_{r−1} ⋯ n_{1}n_{0}⟩_{p}| := n_{r}p^{r} + n_{r−1}p^{r−1} + ⋯ + n_{1}p + n_{0} = n.

Let d_{s}(n) := ∑_{i≥s} n_{i} which is the digit sum starting from the s-th place. We simply let d(n) = d_{0}(n), called the total digit sum.

Lemma 2.1. Let q = p^{k}, t ∈ ℤ_{q}^{∗} and [n]_{p} = ⟨n_{r}n_{r−1} … n_{1}n_{0}⟩_{p}. The p-adic order ω_{p}(n!) and t-encounter function E_{q,t}(n!) are evaluated as follows:

ω_{p}(n!) = \frac{n − d(n)}{p − 1},  (5)
E_{q,t}(n!) = \frac{|⟨n_{r} ⋯ n_{k}n_{k−1}⟩_{p}| − d_{k−1}(n)}{p − 1} + ∑_{i≥0} χ(|⟨n_{i+k−1} ⋯ n_{i+1}n_{i}⟩_{p}| ≥ t).  (6)

Proof. We have

ω_{p}(n!) = ∑_{k=1}^{s}⌊n/p^{k}⌋
= |⟨n_{r}n_{r−1} … n_{2}n_{1}⟩_{p}| + |⟨n_{r}n_{r−1} … n_{2}⟩_{p}| + ⋯ + |⟨n_{r}⟩_{p}|,

because ⌊n/p^{k}⌋ counts the number of integers in [1, n] that are multiples of p^{k}. From this equation, the total contribution to ω_{p}(n!) caused by n_{k} is (p^{k−1} + p^{k−2} + ⋯ + 1)n_{k}. Thus, ω_{p}(n!) = ∑_{k=1}^{s} \frac{(p^{k}−1)}{p−1}n_{k} = ∑_{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 ∈ [1, n] with the same order ω_{p}(m) = i, the sum of their χ(m/p^{i} ≡_{q} t) equals ⌊(⌊\frac{n}{p^{i}} ⌋ + (q − t))/q⌋. 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

E_{q,t}(n!) = ∑_{i≥0} ⌊\frac{⌊\frac{n}{p^{i}} ⌋ + (q − t)}{q}⌋  (7)

= ∑_{i≥k−1} \frac{(p^{i−k+1} − 1)n_{i}}{p − 1} + ∑_{i≥0} χ(|⟨n_{i+k−1} ⋯ n_{i+1}n_{i}⟩_{p}| ≥ t)  (8)

= \frac{|⟨n_{r} ⋯ n_{k}n_{k−1}⟩_{p}| − d_{k−1}(n)}{p − 1} + ∑_{i≥0} χ(|⟨n_{i+k−1} ⋯ n_{i+1}n_{i}⟩_{p}| ≥ t),

where the second summation in (8) counts the effect of the floor function caused by q − t in (7), while the first summation is obtained by ignoring q − t.

Note that equation (5) is the Legendre formula. For convenience, we shall evaluate the two terms in (6) separately. Let E_{q,t}(n!) := E′_{q}(n!) + E′′_{q,t}(n!) by defining

E′_{q}(n!) := \frac{|⟨n_{r} ⋯ n_{k−1}⟩_{p}| − d_{k−1}(n)}{p − 1}, and  (9)
E′′_{q,t}(n!) := ∑_{i≥0} χ(|⟨n_{i+k−1} ⋯ n_{i+1}n_{i}⟩_{p}| ≥ t).  (10)

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 ω_{p}(n!).

The products (m + n)! and (m − n)! also occur frequently in the formulae of various combinatorial numbers. To apply Lemmas 2.1 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 ≥ n and i ≥ j, let us define

β_{p}^{+}(m, n; i, j) := χ(|⟨m_{i}m_{i−1} ⋯ m_{j}⟩_{p}| + |⟨n_{i}n_{i−1} ⋯ n_{j}⟩_{p}| ≥ p^{i−j+1}),
β_{p}^{−}(m, n; i, j) := χ(|⟨m_{i}m_{i−1} ⋯ m_{j}⟩_{p}| < |⟨n_{i}n_{i−1} ⋯ n_{j}⟩_{p}|),

and briefly let β_{p}^{+}(m, n; i) := β_{p}^{+}(m, n; i, 0) and β_{p}^{−}(m, n; i) := β_{p}^{−}(m, n; i, 0), which indicate respectively the possible carry and 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

C_{p}(m, n) := ∑_{i≥0} β_{p}^{+}(m, n; i) and
B_{p}(m, n) := ∑_{i≥0} β_{p}^{−}(m, n; i),

which are respectively the numbers of total carries for (operating) m + n and total borrows for m − n.

Lemma 2.2. Let m, n, i ∈ ℕ with m ≥ n. In the base-p system, we have

d(m + n) = d(m) + d(n) − (p − 1)C_{p}(m, n) and
d(m − n) = d(m) − d(n) + (p − 1)B_{p}(m, n).

Proof. 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} − β_{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} +β_{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 β_{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} + β_{p}^{+}(m, n; i − 1) − p and (m + n)_{i+1} obtains an extra 1 = β_{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.

Now applying Lemmas 2.1 and 2.2, we obtain the following result.

Lemma 2.3. Let n ≥ n and suppose [m]_{p} = ⟨… m_{1}m_{0}⟩_{p} and [n]_{p} = ⟨… n_{1}n_{0}⟩_{p}. Than

ω_{p}((m + n)!) = \frac{m + n − d(m) − d(n)}{p − 1} + C_{p}(m, n) and
ω_{p}((m − n)!) = \frac{m − n − d(m) + d(n)}{p − 1} − B_{p}(m, n).

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 ω_{p} and E_{q,t} to re-prove the following two famous and useful theorems.

Theorem 2.4 (Kummer, 1852 [14]). Let p be a prime and m, n ∈ ℕ with m ≥ n. Then we have

ω_{p}(\binom{m + n}{m}) = C_{p}(m, n) and
ω_{p}(\binom{m}{n}) = B_{p}(m, n).

Proof. By Lemmas 2.1 and 2.3, we derive

ω_{p}(\binom{m + n}{m}) = ω_{p}((m + n)!) − ω_{p}(m!) − ω_{p}(n!)
= [\frac{m + n − d(m) − d(n)}{p − 1} + C_{p}(m, n)] − \frac{m − d(m)}{p − 1} − \frac{n − d(n)}{p − 1}
= C_{p}(m, n).

The proof for ω_{p}(\binom{m}{n}) is similar.

Theorem 2.5 (Lucas, 1877 [17]). The binomial coefficient modulo a prime p can be computed as follows

\binom{m}{n} ≡_{p} ∏_{i≥0} \binom{m_{i}}{n_{i}},

where ⟨⋯ m_{1}m_{0}⟩_{p} and ⟨⋯ n_{1}n_{0}⟩_{p} are the expansions of m and n in the base-p system, respectively.

Proof. We may assume that m_{i} ≥ 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 ω_{p}(\binom{m}{n}) = 0 and (m−n)_{i} = m_{i} −n_{i}. Now applying (4), we see

\binom{m}{n} ≡_{p} ∏_{t∈[1,p−1]} t^{E_{p,t}(m!)−E_{p,t}(n!)−E_{p,t}((m−n)!)}
= ∏_{t∈[1,p−1]} t^{∑^{i≥0}[χ(m_{i}≥t)−χ(n_{i}≥t)−χ((m−n)_{i}≥t)]}  (11)
= ∏_{i≥0} ∏_{t∈[1,p−1]} t^{χ(m_{i}≥t)−χ(n_{i}≥t)−χ(m_{i}−n_{i}≥t)}
= ∏_{i≥0} t^{E_{p,t}(m_{i}!)−E_{p,t}(n_{i}!)−E_{p,t}((m_{i}−n_{i})!)}  (12)

≡_{p} ∏_{i≥0} \binom{m_{i}}{n_{i}}.

Among these equivalences and equations, both (11) and (12) are due to Lemma 2.1 and three E′(·) canceling each other; the last equivalence is because there is no borrow.

The reader can also find a very neat proof of Lucas’ Theorem in [9]. 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, …, 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 ω_{p} and E_{p,t}.

3 Transforming ℤ_{q}^{∗} to an additive group

For performing the power of t and the product ∏ appearing in CF_{p}(n!) ≡_{q} ∏_{t∈ℤ_{q}^{∗}} t^{E_{q,t}(n!)}, we need to work on the domain (ℤ_{q}^{∗}, ×_{q}) (modulo multiplication group). But operating ×_{q} is complicated. We simplify this cumbersome operation by transforming (ℤ_{q}^{∗}, ×_{q}) to an additive group under isomorphism as follows:

(ℤ_{2^{k}}^{∗}, ×_{q}) ≅ (C_{2} × C_{2^{k−2}}, +) for k ≥ 2;  (13)
(ℤ_{p^{k}}^{∗}, ×_{q}) ≅ (C_{p^{k−1}(p−1)}, +) for an odd prime p,  (14)

Table 1: The first few example for the isomorphisms (ℤ_{2^{k}}^{∗}, ×_{q}) ≅ (C_{2} × C_{2^{k−2}}, +)

0 1 0 1 5 1 3 7  0 1 2 3 0 1 5 9 13 1 7 3 15 11

0 1 2 3 4 5 6 7
0 1 5 25 29 17 21 9 13
1 15 11 23 19 31 27 7 3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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

where C_{m} represents a cyclic group of order m. Please, refer to [20] and also see example in Table 1 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.

The multiplication in (ℤ_{q}^{∗}, ×_{q}) is then easily carried out through the corresponding addition in (C_{2} × C_{2^{k−2}}, +). For instance,

7^{5} ×_{16} 11^{15} ≡_{16} T_{16}^{−1}(5 T_{16}(7) + 15 T_{16}(11))
≡_{16} T_{16}^{−1}(5 (1, 0) + 15 (1, 3))
≡_{16} T_{16}^{−1}((1, 0) + (1, 1))
≡_{16} T_{16}^{−1}((0, 1))
≡_{16} 5,

where T_{16} is the isomorphism from ℤ_{16}^{∗} to C_{2} × C_{4} demonstrated in Table 1.

Let q = 2^{k}. The isomorphism

T_{q} : (ℤ_{q}^{∗}, ×_{q}) → (C_{2} × C_{q/4}, +) for k ≥ 2,

is constructed as follows. We use x or (b, u) to denote an element of C_{2} × C_{q/4}, and define T_{q}(t) := x(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) ≡ 0, a constant function.

We assume k ≥ 3 in this paragraph only. Define ℤ_{q}^{∗,1} := {t ∈ ℤ_{q}^{∗} | t ≡_{4} 1} and ℤ_{q}^{∗,3} := {t ∈ ℤ_{q}^{∗} | t ≡_{4} 3}. Clearly, ℤ_{q}^{∗,1} is a subgroup of ℤ_{q}^{∗} and ℤ_{q}^{∗,3} is the unique coset. It is also easy to prove by induction that [5^{(2^{k−2})}]_{2} = ⟨⋯ 1 \underbrace{0 ⋯ 0}_{k − 1 zeros} 1⟩_{2} ≡_{2^{k}} 1 and ℤ_{q}^{∗,1} is a cyclic

group with 5 as a generator. Therefore, we can make

T_{q}(ℤ_{q}^{∗,1}) = {(0, u) | u ∈ C_{q/4}} with T_{q}(5) = (0, 1), and
T_{q}(ℤ_{q}^{∗,3}) = {(1, u) | u ∈ C_{q/4}}.

The reason of no subscript q for b(t) is now clear, because we must have

b(t) = \{ \begin{matrix}0 & if t ≡_{4} 1 \\ 1 & if t ≡_{4} 3 \end{matrix} \} = t_{1} where [t]_{2} = ⟨⋯ t_{2}t_{1}1⟩_{2},  (15)

which is independent on q. The isomorphism u_{q} : ℤ_{q}^{∗,1} → 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} ≡_{q} t. As for those t ∈ ℤ_{q}^{∗,3}, let t̂ ∈ ℤ_{q}^{∗,1} be the unique element satisfying t + t̂ ≡_{q} q/2 and then define u_{q}(t) := u_{q}(t̂). We leave the check that T_{q} is really an isomorphism to the reader.

Let us extend the domain of u_{q} from ℤ_{q}^{∗} to ℤ_{o}, the set of odd integers, by simply defining u_{q}(t) := u_{q}(t (mod q)) for any odd integer t. The following are three fundamental formulae about u_{q}.

Lemma 3.1. Given integers k′ > k ≥ 2 and q′ := 2^{k′}, q := 2^{k}, we have

u_{q′}(t) (mod \frac{q}{4}) = u_{q}(t)  for any t ≡_{4} 1;
u_{q′}(t) (mod \frac{q}{8}) = u_{q}(t) (mod \frac{q}{8}) for any t ≡_{4} 3 and k ≥ 3;
u_{q′}(t) (mod \frac{q}{4}) = u_{q}(t) + \frac{q}{8}χ  for any t ≡_{4} 3 and k ≥ 3,

where χ is either 0 or 1.

Proof. The assertion can be more general by plugging two odd integers t′, t ∈ ℤ_{o} with t′ ≡_{q} t into the both sides of each equation respectively. In case that t′, t ≡_{4} 1, by definition 5^{u_{q′}(t′)} ≡_{q′} t′ ≡_{q} t ≡_{q} 5^{u_{q}(t)} or 5^{u_{q′}(t′)} ≡_{q} 5^{u_{q}(t)} in short. Since 5 is a generator of ℤ_{q}^{∗,1} with order \frac{q}{4}. Thus, u_{q′}(t′) ≡_{q/4} u_{q}(t) and the first equation (not equivalence) holds because u_{q}(t) ∈ [0, \frac{q}{4} − 1].

Suppose t′ ≡_{q} t and both t′, t ≡_{4} 3. We find the two numbers t̂′, t̂≡_{4} 1 with t̂′ ≡_{q′} \frac{q′}{2} − t′ and t̂ ≡_{q} \frac{q}{2} − t, so that u_{q′}(t′) := u_{q′}(t̂′) and u_{q}(t) := u_{q}(t̂) by definition. Clearly, t̂′ ≡_{q/2} t̂; so we can plug these two respectively into the both sides of the first equation of the lemma. Thus, we get u_{q′}(t̂′) (mod \frac{q}{8}) = u_{q/2}(t̂) and then reach the general version of the second equation of the lemma as follows

u_{q′}(t′) (mod \frac{q}{8}) = u_{q/2}(t) = u_{q}(t) (mod \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.

Directly from Table 1, we have

\begin{aligned}u_{8}(t) & = & t_{2}, and \\ u_{16}(t) & = & t_{1} + t_{2} + 2t_{3} − 2t_{1}t_{2}. \end{aligned}  (16)

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:

T_{q}^{−1}(b, u) ≡_{q} \{ \begin{matrix}5^{u} & if b = 0 \\ 2^{k−1} − 5^{u} & if b = 1 \end{matrix} \} ≡_{q} 2^{k−1}b + (−1)^{b}5^{u} for k ≥ 2.  (17)

T_{2^{k}}(CF_{2}(n!)) and T_{2^{k}}(CF_{2}(c_{n}))

The argument in this subsection will show a difference in T_{p^{k}}(CF_{p}(·)) 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 ℤ_{q}^{∗} to the set of odd integers, by simply define u_{q}(t) := u_{q}(t (mod q)). In general, we have

T_{q}(CF_{2}(∏_{i=1}^{a} M_{i})) = ∑_{t∈ℤ_{q}^{∗}} E_{q,t}(∏_{i=1}^{a} M_{i}) T_{q}(t)  (18)

= ∑_{x∈C_{2}×C_{q/4}} E_{q,T_{q}^{−1}(x)}(∏_{i=1}^{a} M_{i}) x.  (19)

Any term of E_{q,t}(∏_{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:

∑_{x∈C_{2}×C_{q/4}} x = |C_{q/4}| ∑_{b∈C_{2}}(b, 0) + |C_{2}| ∑_{u∈C_{q/4}}(0, u) = 2^{k−2}(1, 0) + 2 (0, 2^{k−3}) = (0, 0), (20)

when k ≥ 3. A corresponding property is that

∏_{t∈ℤ_{2^{k}}^{∗}} t = 1 for k ≥ 3 or k = 1.  (21)

By Lemma 2.1, the partial term E′_{q}(n!) is independent on t; so we have ∑_{x∈C_{2}×C_{q/4}} E′_{q}(n!) x = (0, 0) and we can ignore E′_{q}(n!). Thus, if the formal product is n!, we improve (18) by a better formula as follows:

T_{q}(CF_{p}(n!)) = (b(CF_{p}(n!), u_{q}(CF_{p}(n!)) = ∑_{t∈ℤ_{q}^{∗}} E′′_{q,t}(n!) (b(t), u_{q}(t)).  (22)

However, the property (21) fails when k = 2 or p is an odd prime; so (22) does not work in this condition.

As for k = 2, not only the isomorphism ℤ_{4}^{∗} ≅ C_{2} is trivial, but also

CF_{2}(n!) ≡_{4} (−1)^{E_{4,3}(n!)} = (−1)^{r(n)+n_{0}+n_{1}} = (−1)^{d_{2}(n)+c_{2}(n)},  (23)

shown by Lemma 2.1 in [8], is a easy formula. Apart from n_{0}, n_{1} and d_{2}, we have not defined some new notation in (23) yet. Over the sequence [n]_{2}, let r(n) be the number of runs of 1, and let c_{2}(n) := ∑_{i≥0} χ(n_{i} = n_{i+1} = 1), i.e., the number of the consecutive pairs of 1. The last equality in (23) is due to the simple fact that c_{2}(n) = d(n) − r(n). By (15) and (23), we conclude that

b(CF_{2}(n!)) ≡_{2} r(n) + n_{0} + n_{1} ≡_{2} d_{2}(n) + c_{2}(n) ≡_{2} zr(n) + n_{1}.  (24)

The last equivalence will be explained later in (28).

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 [8].

4 b(CF_{2}(n!)) and u_{8}(CF_{2}(n!)); Catalan numbers modulo 8

Given a multi-subset M and a subset T of ℤ_{q}, let #(M, T) be the number of elements (with multiplicity) in M belonging to T. Define a multi-set

S_{k}(n) := {|⟨n_{k+i−1} … n_{i+1}n_{i}⟩_{2}|}_{i=0}^{r},

where [n]_{2} = ⟨n_{r} ⋯ n_{1}n_{0}⟩_{2} and ⟨n_{k+i−1} … n_{i+1}n_{i}⟩_{2} is a k-segment contained in the se-

quence ⟨\overbrace{0 ⋯ 00}^{k−1} n_{r} ⋯ n_{1}n_{0}⟩_{2}. For example, given [n]_{2} = ⟨100110000101⟩_{2} we have S_{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 #(S_{3}(n), {3, 4}) = 3.

The following counting formulae for #(S_{3}(n), {t}) are easy to check.

#(S_{3}(n), {3}) = ∑_{i≥0} χ(⟨n_{i+2}n_{i+1}n_{i}⟩ = ⟨011⟩) = r(n) − r_{1}(n);  (25)
#(S_{3}(n), {4}) = ∑_{i≥0} χ(⟨n_{i+2}n_{i+1}n_{i}⟩ = ⟨100⟩) = zr(n) − zr_{1}(n);  (26)
#(S_{3}(n), {5}) = ∑_{i≥0} χ(⟨n_{i+2}n_{i+1}n_{i}⟩ = ⟨101⟩) = zr_{1}(n) − n_{1}(1 − n_{0});
#(S_{3}(n), {6}) = ∑_{i≥0} χ(⟨n_{i+2}n_{i+1}n_{i}⟩ = ⟨110⟩) = r(n) − r_{1}(n) − n_{0}n_{1},

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 (10), (22) and Table 1 for ℤ_{8}^{∗} ≅ C_{2} × C_{2}, we derive

E′′_{8,3}(n!) (1, 0) = (∑_{i≥0} χ(|⟨n_{i+2}n_{i+1}n_{i}⟩_{p}| ≥ 3), 0) = (#(S_{3}(n), {3, 4, 5, 6, 7}), 0),
E′′_{8,5}(n!) (0, 1) = (0, ∑_{i≥0} χ(|⟨n_{i+2}n_{i+1}n_{i}⟩_{p}| ≥ 5) = (0, #(S_{3}(n), {5, 6, 7})), and
E′′_{8,7}(n!) (1, 1) = [ ∑_{i≥0} χ(|⟨n_{i+2}n_{i+1}n_{i}⟩_{p}| ≥ 7)](1, 1) = (#(S_{3}(n), {7}), #(S_{3}(n), {7})).

Summing up the above three, we obtain

T_{8}(CF_{2}(n!)) = (b(CF_{2}(n!)), u_{8}(CF_{2}(n!)))
= (#(S_{3}(n), {3, 4, 5, 6}), #(S_{3}(n), {5, 6})) (mod 2)  (27)
= (zr(n) + n_{1}, r(n) + r_{1}(n) + zr_{1}(n) + n_{1}) (mod 2)  (28)
= (r(n) + n_{0} + n_{1}, r(n) + r_{1}(n) + zr_{1}(n) + n_{1}) (mod 2).  (29)

The last equation is due to the fact r(n) = zr(n) + n_{0}. This equation also explains the last equivalence in (24). 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 [8], through an easier approach.

Theorem 4.1 (Eu, Liu and Yeh, 2008 [8]). Let c_{n} be the n-th Catalan number. Then c_{n} ≢_{8} 3, 7 for any n. And for the other congruences, we have

c_{n} ≡_{8} \{ \begin{matrix}1 & if n = 0 or 1; \\ 2 & if n = 2^{a} + 2^{a+1} − 1 for some a ≥ 0; \\ 4 & if n = 2^{a} + 2^{b} + 2^{c} − 1 for some c > b > a ≥ 0; \\ 5 & if n = 2^{a} − 1 for some a ≥ 2; \\ 6 & if n = 2^{a} + 2^{b} − 1 for some b − 2 ≥ a ≥ 0; \\ 0 & otherwise. \end{matrix}

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 2.1 we have

ω_{2}(c_{n}) = [2n − d(2n)] − ω_{2}(n + 1) − 2[n − d(n)]
= 2n − d(n) − min{i | n_{i} = 0} − 2n + 2d(n)
= d(n) − min{i | n_{i} = 0}
= d(n + 1) − 1.

The last equation is due to the fact that min{i | 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 4.1, the above result for ω_{2}(c_{n}) provides a new proof of the next theorem.

Theorem 4.2 (Deutsch and Sagan, 2006 [4]). For n ∈ ℕ we have

ω_{2}(c_{n}) = d(n + 1) − 1 = d(n) − min{i | n_{i} = 0}.

When we deal with c_{n} modulo 2^{k}, this theorem suggests that [n]_{2} be bisected into two particular segments as follows:

⟨ \overbrace{10 ⋯ 1100}^{The rightmost is a 0.} \underbrace{1 ⋯ 1}_{This segment of all 1 might be empty.} ⟩_{2}  (30)

We call these two segments the principal segments of [n]_{2} and use [2α]_{2} and ⟨1^{β}⟩_{2} to denote them respectively, where α, β ∈ ℕ and 1^{β} means a string of 1 of length β. We use 2α because its 0-th place digit must be 0. Equivalently, we can also define

α := \frac{CF_{2}(n + 1) − 1}{2}, and
β := ω_{2}(n + 1) = min{i | n_{i} = 0}.

Here we find that the notation α is good to use in the following property which directly follows Theorem 4.2.

Corollary 4.3. In general, we have ω_{2}(c_{n}) = d(α). In particular, c_{n} ≡_{q} 0 if and only if d(α) ≥ k, and c_{n} ≡_{q} q/2 if and only if d(α) = k − 1.

Due to this corollary, from now on we focus only on d(α) ≤ k − 2. Let us examine T_{8}(CF_{2}(n!)). Its first entry is enumerated by using (15) and (24) as follows:

b(CF_{2}(c_{n})) ≡_{2} [zr(2n) + (2n)_{1}] − b(CF_{2}(n + 1)) − 2[zr(n) + n_{1}]
≡_{2} [(zr(n) + n_{0}) + n_{0}] + b(2α + 1)
≡_{2} zr(n) + α_{0}
≡_{2} (zr(α) + α_{0}) + α_{0}
≡_{2} zr(α).  (31)

Since b(CF_{2}(c_{n})) is independent on q, this identity derives a general formula as follows.

Theorem 4.4. Let n ∈ ℕ, q = 2^{k} with k ≥ 2, and α = (CF_{2}(n + 1) − 1)/2. Then we have

c_{n} ≡_{q} (−1)^{zr(α)}2^{d(α)}5^{u_{q}(CF_{2}(c_{n}))}.  (32)

In particular, when k = 2 we have

c_{n} ≡_{4} (−1)^{zr(α)}2^{d(α)}.  (33)

Proof. By (17), Theorem 4.2 (or Corollary 4.3) and the result of b(CF_{2}(c_{n})) in (31), we have

c_{n} ≡_{q} 2^{ω_{2}(c_{n})}[2^{k−1}b + (−1)^{b}5^{u}]
≡_{q} 2^{d(α)}[2^{k−1}zr(α) + (−1)^{zr(α)}5^{u_{q}(CF_{2}(c_{n}))}].

We finish the proof of the first assertion after considering two cases: d(α) = 0 (which implies zr(α) = 0) and d(α) ≥ 1. Notice that u_{4}(t) = 0 and then the second assertion follows. The equivalence (33) is actually a rewrite of Eu, Liu and Yeh’s result in [8]. The immediate

consequence that c_{n} ≢_{4} 3 was also given by them. The following two auxiliary corollaries directly follows Theorem 4.4.

Corollary 4.5. Let n, k ∈ ℕ with k ≥ 3, α = (CF_{2}(n + 1) − 1)/2 and d(α) = k − 2. We have

c_{n} ≡_{q} (−1)^{zr(α)} \frac{q}{4}.

Corollary 4.6. Let n ∈ ℕ and α = (CF_{2}(n + 1) − 1)/2. We have

CF_{2}(c_{n}) ≡_{4} (−1)^{zr(α)}.

Corollary 4.5 solves the case d(α) = k − 2 and is an improvement of Corollary 4.3. We will deal with the case d(α) = k − 3 by Corollary 5.4 in the next section.

Formula (32) offers a general method to enumerate c_{n} (mod 2^{k}), but it does not offer the classification like Theorem 4.1. On the other hand, Table 1 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:

u_{8}(CF_{2}(c_{n})) ≡_{2} [r(2n) + r_{1}(2n) + zr_{1}(2n) + (2n)_{1}] − u_{8}(CF_{2}(n + 1))  (34)
−2[r(n) + r_{1}(n) + zr_{1}(n) + n_{1}]
≡_{2} r(n) + r_{1}(n) + [zr_{1}(n) + n_{0} − n_{1}(1 − n_{0})] + n_{0} + u_{8}(2α + 1)
= [r(α) + χ(β ≥ 1)] + [r_{1}(α) + χ(β = 1)] + [zr_{1}(α) + α_{0} − α_{1}(1 − α_{0})]
−[χ(β ≥ 2) + χ(α = 1)χ(β = 0)]χ(β = 0) + α_{1}
≡_{2} χ(β ≥ 2) + χ(α = 1, β = 0) + r(α) + r_{1}(α) + zr_{1}(α) + α_{0}(1 − α_{1}). (35)

By the formula of u_{8}(CF_{2}(c_{n})), we can finish the mission of this section. Let us rewrite Theorem 4.1 in a new format using α and β as follows. The equivalence of these two theorems is easy to check.

Theorem 4.7. Given n ∈ ℕ, let α = \frac{CF_{2}(n+1)−1}{2} and β = min\{i | n_{i} = 0\}. We have

c_{n} ≡_{8} \{ \begin{matrix}\begin{matrix}1 \\ 5 \end{matrix} \} if & d(α) = 0 and \{ \begin{matrix}β = 0 or 1, \\ β ≥ 2, \end{matrix} \\ \begin{matrix}2 \\ 6 \end{matrix} \} if & d(α) = 1 and \{ \begin{matrix}α = 1, \\ α ≥ 2, \end{matrix} \\ 4  if & d(α) = 2, \\ 0  if & d(α) ≥ 3. \end{matrix}

Proof. The congruences 0, 2, 4 and 6 can be easily solved by Corollaries 4.3 and 4.5. The only remaining case is d(α) = 0. In this case, every term related to α turns to be 0 in (35). Then plug into (32) and obtain

c_{n} ≡_{8} (−1)^{0}2^{0}5^{χ(β≥2)} ≡_{8} 5^{χ(β≥2)}.

Therefore, c_{n} ≡_{8} 1 if and only if [n]_{2} = ⟨1⟩_{2} or it is an empty sequence, and c_{n} ≡_{8} 5 if and only if [n]_{2} = ⟨1^{β}⟩_{2} for β ≥ 2. The proof is complete now.

5 u_{16}(CF_{2}(n!)); Catalan numbers modulo 16

Since we already know ω(c_{n}) = d(α) and b(CF_{2}(c_{n})) = zr(α), 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 (10) and (22), we derive that

u_{q}(CF_{2}(n!)) ≡_{q/4} ∑_{t∈ℤ_{q}^{∗}} E′′_{q,t}(n!) u_{q}(t)
= ∑_{t∈ℤ_{q}^{∗}} χ(|⟨n_{i+k−1} ⋯ n_{i+1}n_{i}⟩_{2}| ≥ t) u_{q}(t)
= ∑_{t∈ℤ_{q}^{∗}} #(S(n), [t, q − 1]) u_{q}(t)
= ∑_{s∈[1,q−1]} #(S(n), {s}) ∑_{t∈[1,s]_{o}} u_{q}(t)  (36)
= ∑_{s∈[3,q−2]} #(S(n), {s}) ∑_{t∈[3,s]_{o}} u_{q}(t)  (37)
= ∑_{s∈[3,q−3]_{o}} #(S(n), {s, s + 1}) ∑_{t∈[3,s]_{o}} u_{q}(t)  (38)

where [1, s]_{o} is the set of odd integers in [1, s]. Note that ∑_{t∈[1,s]_{o}} u_{q}(t) = ∑_{t∈[3,s]_{o}} u_{q}(t) for u_{q}(1) = 0. For this reason, we eliminate s = 1, 2 in the first summation of (36). Moreover, we eliminate s = q − 1 because ∑_{t∈[1,q−1]_{o}} u_{q}(t) = 0 (see the second entry in (20)). The last formula (38) is because ∑_{t∈[3,s]_{o}} u_{q}(t) = ∑_{t∈[3,s+1]_{o}} u_{q}(t) for any odd s.

Depending on k, there are several kinds of k-segments (we mean [t]_{2} for t ∈ [0, q − 1]) irrelevant to the counting in (37). For example, we see in (27) 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} = ⟨0^{k}⟩_{2} and [q − 1]_{2} = ⟨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:

Theorem 5.1. Given n ∈ ℕ, let m be an integer such that [m]_{2} is obtained by either extending or truncating some runs of 0 or 1 of length ≥ k − 1 in [n]_{2} to be different length but still ≥ 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!) ≡_{q} CF_{2}(m!).

Proof. 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!)) ≡_{2} zr(n) + n_{1} together with zr(n) = zr(m) and n_{1} = m_{1}. The last equivalence is a direct consequence.

We use ṅ to denote the integer such that [ṅ]_{2} is obtained by truncating every run of 1 of length ≥ k in [n]_{2} to be exactly length k −1, without changing any run of 0. Also let 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} = ⟨100011101111⟩_{2} then [ṅ]_{2} = ⟨100011011⟩_{2} and [n̈]_{2} = ⟨10011011⟩_{2}. Note that both ṅ and n̈ depend on k, but we do not mark k for convenience. To avoid confusion, it should be remembered which k is discussed.

From (37), let us use the isomorphism ℤ_{16}^{∗} ≅ C_{2} × C_{4} in Table 1 to construct a new table as follows:

\begin{matrix}s ∈ [3, 13]_{o} ⊆ ℤ_{16}^{∗} & 3 & 5 & 7 & 9 & 11 & 13 \\ u_{16}(s) ∈ C_{4} & 1 & 1 & 0 & 2 & 3 & 3 \\ ∑_{t∈[3,s]_{o}} u_{16}(s) (mod 4) & 1 & 2 & 2 & 0 & 3 & 2 \end{matrix}

The last row of this table records the accumulations according to the second row. Now plug these accumulations into (38) and Lemma 5.1 to obtain

u_{16}(CF_{2}(n!)) ≡_{4} #(S_{4}(ṅ), {3, 4}) + 2#(S_{4}(ṅ), {5, 6, 7, 8, 13, 14}) + 3#(S_{4}(ṅ), {11, 12})
= #(S_{4}(ṅ), {3, 4, 5^{2}, 6^{2}, 7^{2}, 8^{2}, 11^{3}, 12^{3}, 13^{2}, 14^{2}})  (39)

where the second line is a comprehensible modification for #(·, ·) 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 ṅ with n̈ in this formula.

Since formula (39) 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 #(S_{4}(ṅ, {·}), and x means an unspecified binary digit.

A := #(S_{4}(ṅ), {4}) + 2#(S_{4}(ṅ), {5, 6, 7})
= #(S_{4}(ṅ), {⟨0100⟩_{2}}) + 2[#(S_{4}(ṅ), {⟨01xx⟩_{2}}) − #(S_{4}(ṅ), {⟨0100⟩_{2}})]
= 2r(⌊\frac{ṅ}{4}⌋) − #(S_{4}(ṅ), \{⟨0100⟩_{2}\})
= 2[r(ṅ) − ṅ_{1}(1 − ṅ_{2}) − ṅ_{0}(1 − ṅ_{1})] − #(S_{4}(ṅ), {⟨0100⟩_{2}});

B := 3#(S_{4}(ṅ){12}) + 2#(S_{4}(ṅ), {13, 14}),
= 3#(S_{4}(ṅ){⟨1100⟩_{2}}) + 2[#(S_{4}(ṅ), {⟨11xx⟩_{2}}) − #(S_{4}(ṅ), {⟨1100⟩_{2}})] (40)
= 2#(S_{4}(ṅ), {⟨11xx⟩_{2}}) + #(S_{4}(ṅ){⟨1100⟩_{2}})
= 2c_{2}(⌊\frac{ṅ}{4}⌋) + #(S_{4}(ṅ), \{⟨1100⟩_{2}\})
= 2[c_{2}(ṅ) − ṅ_{0}ṅ_{1} − ṅ_{1}ṅ_{2}] + #(S_{4}(ṅ), {⟨1100⟩_{2}});
C := #(S_{4}(ṅ), {3}) − #(S_{4}(ṅ), {11})
= #(S_{4}(ṅ), {⟨0011⟩_{2}}) − [#(S_{4}(ṅ), {⟨x011⟩_{2}}) − #(S_{4}(ṅ), {⟨0011⟩_{2}})]
= 2#(S_{4}(ṅ), {⟨0011⟩_{2}}) − #(S_{3}(ṅ), {⟨011⟩_{2}})
= 2#(S_{4}(ṅ), {⟨0011⟩_{2}}) − r(ṅ) + r_{1}(ṅ);  (41)
D := 2#(S_{4}(ṅ), {8})
= 2#(S_{4}(ṅ), {⟨1000⟩_{2}})

We obtain (40) because ⟨11xx⟩_{2} has four types [12]_{2}, [13]_{2}, [14]_{2}, and [15]_{2} = ⟨1111⟩_{2}, but 15 never appears in S_{4}(ṅ) for the truncation property of ṅ. We obtain (41) by referring to (25). Now collecting the four results above with a simple arrangement and referring to (26), we obtain

u_{16}(CF_{2}(n!)) ≡_{4} u_{16}(CF_{2}(ṅ!)  (42)
≡_{4} 2[r(ṅ) + c_{2}(ṅ) + ṅ_{0} + ṅ_{1} + #(S_{4}(ṅ), {⟨0011⟩_{2}, ⟨1100⟩_{2}, ⟨1000⟩_{2}})]
+r_{1}(ṅ) − r(ṅ) − #(S_{4}(ṅ), {⟨0100⟩_{2}, ⟨1100⟩_{2}})
= 2[c_{2}(ṅ) + ṅ_{0} + ṅ_{1} + #(S_{4}(ṅ), {⟨0011⟩_{2}, ⟨1x00⟩_{2}})]
+r_{1}(ṅ) + r(ṅ) + zr_{1}(ṅ) − zr(ṅ).  (43)

Remark. In (40), we do use the property that [ṅ]_{2} contains no sub-sequence ⟨1^{4}⟩_{2}, whereas it does not matter for the existence of ⟨0^{4}⟩_{2} in [ṅ]_{2}. Therefore, to apply (43), 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 ≥ 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α]_{2} and ⟨1^{β}⟩_{2} defined in (30). Similarly, [ṅ]_{2} also has its own two principal segments, which shall be [2α̇]_{2} and ⟨1^{β′}⟩_{2} with β′ = min{β, 3}. We have

u_{16}(CF_{2}(n + 1)) = u_{16}(2α + 1) = u_{16}(2α̇ + 1) = u_{16}(CF_{2}(ṅ + 1)),

where the two u_{16}’s are equal because they depend respectively on the identical 3-segments ⟨α_{2}α_{1}α_{0}⟩_{2} and ⟨α̇_{2}α̇_{1}α̇_{0}⟩_{2} (see (16)). This is why we use ṅ instead of n̈. Actually, the only situation we are concerned about is that α ≠ 0 and ⟨α_{2}α_{1}α_{0}⟩_{2} = ⟨000⟩_{2}. For instance, let [n]_{2} = ⟨100001⟩_{2}, and so [ṅ]_{2} = ⟨100001⟩_{2} and [n̈]_{2} = ⟨10001⟩_{2}. We have u_{16}(CF (n + 1)) = u_{16}(CF (ṅ + 1)) = 0 but u_{16}(CF (n̈ + 1)) = 2. Using 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 ∈ ℕ, let n̄ be the integer such that [n̄]_{2} is obtained by the following rules.

a. When the rightmost run of 0 in [n]_{2} is of length ≥ k + 1, let us truncate it to be length k, otherwise keep it the same.

b. For any other run of 0 or 1 of [n]_{2} with length ≥ k, truncate them to be length k − 1.

Suppose [n]_{2} is interpreted as its two principal segments [2α]_{2} and ⟨1^{β}⟩_{2} defined in (30). Interestingly, the corresponding two segments of [n̄]_{2} are exactly [2α̈] and ⟨1^{β′}⟩_{2}, where β′ = min{β, k − 1}. Moreover, we have

u_{q}(CF_{2}((2n)!)) ≡_{q/4} u_{q}(CF_{2}( ¯2n!)) ≡_{q/4} u_{q}(CF_{2}((2n̄)!)).  (44)

The second equivalence is a little bit complicated and takes time to understand. It is better to refer to the last remark.

Theorem 5.2. Let n, k ∈ ℕ with k ≥ 3 and α = (CF_{2}(n + 1) − 1)/2. We have

c_{n} ≡_{2^{k}} \{ \begin{matrix}cn̄ & for d(α) ≤ k − 1, and \\ 0 & for d(α) ≥ k. \end{matrix}

Proof. By Theorem 4.4, c_{n} ≡_{2^{k}} (−1)^{zr(α)}2^{d(α)}5^{u_{q}(CF_{2}(c_{n}))}; so the condition for c_{n} ≡_{2^{k}} 0 is trivial. Considering d(α) ≤ k − 1 and using the fact that cn̄ ≡_{2^{k}} (−1)^{zr(α̈)}2^{d(α̈)}5^{u_{q}(CF_{2}(cn̄))}. we obtain that d(α) = d(α̈) and zr(α) = zr(α̈). The proof immediately follows, after we derive

u_{q}(CF_{2}(c_{n})) =  u_{q}(CF_{2}((2n)!)) − u_{q}(CF_{2}(n + 1)) − 2 u_{q}(CF_{2}(n!))
≡_{q/4} u_{q}(CF_{2}((2n̄)!)) − u_{q}(CF_{2}(2α + 1)) − 2 u_{q}(CF_{2}(n̄!))
≡_{q/4} u_{q}(CF_{2}((2n̄)!)) − u_{q}(CF_{2}(2α̈ + 1)) − 2 u_{q}(CF_{2}(n̄!))
=  u_{q}(CF_{2}(cn̄)).

Remark. 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 5.2 supports a negative answer as follows.

Theorem 5.3. Let k ≥ 2 and q = 2^{k}. (a) If there exists δ ∈ [0, k−1] such that k^{δ+1} < 2^{k−δ−1}, then there exists N ∈ [0, q − 1] with ω(N) = δ such that c_{n} ≢_{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 + ∑_{δ=0}^{k−1} min(k^{δ+1}, 2^{k−δ−1}).

Proof. To prove part (a), we need to find a upper bound for the cardinality of {[n̄]_{2} | n ∈ ℕ with ω_{2}(c_{n}) = δ}. As usual, we split [n]_{2} into two principal segments, [2α]_{2} and ⟨1^{β}⟩_{2}. We are provided by d(α) = ω_{2}(c_{n}) = δ ≤ k − 1. In the same way, [n̄]_{2} has its own principal segments, which must be [2α̈] and ⟨1^{β′}⟩_{2} with d(α̈) = δ and β′ = min{β, k −1}. The last two identities suggest the possible types of [n̄]_{2}. There are k^{δ} possible α̈, and k possible β′; so we have k^{δ+1} possible n̄. On the other hand, there are at most 2^{k−δ−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} ≢_{4} 3. For k ≥ 3, jut let δ = 0 and then k^{δ+1} = k < 2^{k−1} is always true. The bound for the cardinality is a direct result from part (a).

This property appeared in Theorem 4.7 as (k, δ) = (3, 0). It will appear again in Theorem 5.5 as (k, δ) = (4, 0) and in Theorem 6.6 as (k, δ) = (6, 0). However, in Theorem 6.4 we have k^{δ+1} > 2^{k−δ−1} provided by (k, δ) = (6, 1), but some congruence numbers are still missing.

Using (44) and also plugging n̄ into (43) instead of ṅ, we derive that

u_{16}(CF_{2}(c_{n})) ≡_{4} u_{16}(CF_{2}((2n̄)!)) − 2u_{16}(CF_{2}(n̄!)) − u_{16}(CF_{2}(n̄ + 1))  (45)
≡_{4} 2[c_{2}(n̄) + n̄_{0} + n̄_{2} + n̄_{0}n̄_{2} + #(S_{4}(n̄), {⟨0011⟩_{2}, ⟨1x00⟩_{2}})]
−r_{1}(n̄) − r(n̄) − zr_{1}(n̄) + zr(n̄) − n̄_{1} + n̄_{0}n̄_{1} − u_{16}(CF_{2}(2α̈ + 1))
≡_{4} 2[c_{2}(n̄) + (1 − n̄_{0})(1 − n̄_{2}) + #(S_{4}(n̄), {⟨0011⟩_{2}, ⟨1x00⟩_{2}})]
+1 − r_{1}(n̄) − zr_{1}(n̄) + (1 − n̄_{0})(1 − n̄_{1}) − [α̈_{0} + α̈_{1} + 2α̈_{2} − 2α̈_{0}α̈_{1}] (46)
≡_{4} χ(β′ = 0)(2α̈_{1} − α̈_{0} − 1) − χ(β′ = 1) + 2χ(β′ = 2)α̈_{0} + 2χ(β′ = 3)(1 − α̈_{0})
+2[c_{2}(α̈) + α̈_{0}(1 − α̈_{2}) + #(S_{4}(α̈), {⟨0011⟩_{2}, ⟨1x00⟩_{2}})] − r_{1}(α̈)
−zr_{1}(α̈) + α̈_{0}α̈_{1} + 1.  (47)

To derive (46), we need the identity r(n̄) − zr(n̄) = n̄_{0} and refer to (16). With the help of (47), we can turn d(α) = k − 3 to be a solved case for the problem of c_{n} (mod q).

Corollary 5.4. Let n, k ∈ ℕ, α = (CF_{2}(n + 1) − 1)/2 and k − d(α) = 3. Then we have

c_{n} ≡_{q} (−1)^{zr(α)}[2^{k−3} + 2^{k−1}u_{16}(CF_{2}(c_{n}))].  (48)

Proof. Let us apply Theorem 4.4 and derive that

c_{n} ≡_{q} (−1)^{zr(α)}2^{d(α)}(1 + 4)^{u_{q}(CF_{2}(c_{n}))}
≡_{q} (−1)^{zr(α)}2^{k−3}[1 + 4 u_{q}(CF_{2}(c_{n}))]
≡_{q} (−1)^{zr(α)}2^{k−3}[1 + 4 u_{16}(CF_{2}(c_{n}))],

where the last equivalence is due to u_{q}(t) ≡_{2} u_{16}(t), a result of Lemma 3.1.

Finally, we state and prove our main result of this section.

Theorem 5.5. Let c_{n} be the n-th Catalan number. First of all, c_{n} ≢_{16} 3, 7, 9, 11, 15 for any n. As for the other congruences, we have

c_{n} ≡_{16} \{ \begin{matrix}\begin{matrix}1 \\ 5 \\ 13 \end{matrix} \} if & d(α) = 0 and \{ \begin{matrix}β ≤ 1, \\ β = 2, \\ β ≥ 3, \end{matrix} \\ \begin{matrix}2 \\ 10 \end{matrix} \} if & d(α) = 1, α = 1 and \{ \begin{matrix}β = 0 or β ≥ 2, \\ β = 1, \end{matrix} \\ \begin{matrix}6 \\ 14 \end{matrix} \} if & d(α) = 1, α ≥ 2 and \{ \begin{matrix}(α = 2, β ≥ 2) or (α ≥ 3, β ≤ 1), \\ (α = 2, β ≤ 1) or (α ≥ 3, β ≥ 2), \end{matrix} \\ \begin{matrix}4 \\ 12 \end{matrix} \} if & d(α) = 2 and \{ \begin{matrix}zr(α) ≡_{2} 0, \\ zr(α) = 1, \end{matrix} \\ 8  if & d(α) = 3, \\ 0  if & d(α) ≥ 4. \end{matrix}

where α = (CF_{2}(n + 1) − 1)/2 and β = ω_{2}(n + 1) (or β = min{i | n_{i} = 0}).

Proof. Congruences 0, 4, 8 and 12 are trivial cases. Suppose d(α) = 1 (so α ≥ 1). Here b(CF_{2}(c_{n})) = zr(α) can only be 0 or 1 depending on α = 1 or α ≥ 2 respectively. Moreover, u_{8}(CF_{2}(c_{n})) ≡_{2} χ(α = 2) + χ(β = 1) + χ(α ≥ 2)χ(β ≥ 1) by (35). Let us use the following table of (b(CF_{2}(c_{n})), u_{8}(CF_{2}(c_{n}))) for discussion.

α = 1 α = 2 α ≥ 3
β = 0 (0,0) (1,1) (1,0)
β = 1 (0,1) (1,1) (1,0)
β ≥ 2 (0,0) (1,0) (1,1)

We conclude the congruences 2, 6, 10, 14 by using this table and referring to the isomorphism Z_{8}^{∗} ≅ C_{2} × C_{2} in Table 1. For instance, if (α, β) = (2, 1) then (b(CF_{2}(c_{n})), u_{8}(CF_{2}(c_{n}))) = (1, 1). Hence CF_{2}(c_{n}) ≡_{8} 7 and then c_{n} ≡_{16} 2 × 7 = 14. For d(α) = k − 3, we can also use Lemma 5.4 to obtain the same result.

Now suppose d(α) = 0. Clearly, α = 0 and b(CF_{2}(c_{n})) = zr(α) = 0. Let us adopt a new notation n̄ such that [2α̈]_{2} and ⟨1^{β′}⟩_{2} are the principal segments of [n̄]_{2}. Notice that β′ = min{β, 3}. Since α̈ = 0 (due to α = 0), every term involving α̈ in (47) turns to 0. Thus, we have u_{16}(CF_{2}(c_{n})) = −χ(β′ = 0) − χ(β′ = 1) + 2χ(β′ = 3) + 1, which equals 0, 0, 1, 3 if β′ = 0, 1, 2, 3 respectively. The congruences 1, 5, 13 are done by case-discussion and referring to Table 1.

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 4.1, but the lack of 9 is a new result.

6 u_{32}(CF_{2}(n!)) and u_{64}(CF_{2}(n!)); c_{n} (mod 64)

First, let us show the easy cases without proof: c_{n} ≡_{64} 0, 16.32 or 48, as provided by d(α) ≥ 4.

Theorem 6.1. Given n ∈ ℕ with α = (CF_{2}(n + 1) − 1)/2, we have

c_{n} ≡_{64} \{ \begin{matrix}\begin{matrix}16 \\ 48 \end{matrix} \} if & d(α) = 4 and \{ \begin{matrix}zr(α) ≡_{2} 0 \\ zr(α) ≡_{2} 1, \end{matrix} \\ 32  if & d(α) = 5, \\ 0  if & d(α) ≥ 6. \end{matrix}

The next class is for c_{n} ≡_{64} 8, 24, 40 or 56.

Theorem 6.2. Given n ∈ ℕ with d(α) = 3, we suppose [α]_{2} = ⟨10^{a}10^{b}10^{c}⟩_{2}, i.e., [n]_{2} = ⟨10^{a}10^{b}10^{c+1}1^{β}⟩_{2}. Also we define

B := χ(a ≥ 1) + χ(b ≥ 1) + χ(c ≥ 1) and
U := χ(a = 1) + χ(b = 1) + χ(c = 1) + χ(b ≥ 1)[χ(a ≥ 1) + χ(c = 0)] + χ(β ≥ 2) + 1.

Then we have

c_{n} ≡_{64} \{ \begin{matrix}8 if & B ≡_{2} 0 and & U ≡_{2} 0, \\ 24 if & B ≡_{2} 1 and & U ≡_{2} 0, \\ 40 if & B ≡_{2} 0 and & U ≡_{2} 1, \\ 56 if & B ≡_{2} 1 and & U ≡_{2} 1. \end{matrix}

or simply

c_{n} ≡_{64} 8 × [4χ(U ≡_{2} 1) + 2χ(B ≡_{2} 1) + 1].

Proof. Because d(α) = 3 we have ω_{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 (31) and (35) to interpret T_{8}(CF_{2}(c_{n})) as follows:

b(CF_{2}(c_{n})) ≡_{2} zr(α) = χ(a ≥ 1) + χ(b ≥ 1) + χ(c ≥ 1),

which is B, and

u_{8}(CF_{2}(c_{n})) ≡_{2} χ(β ≥ 2) + χ(α = 1, β = 0) + r(α) + r_{1}(α) + zr_{1}(α) + α_{0}(1 − α_{1})
= χ(β ≥ 2) + 0 + [1 + χ(a ≥ 1) + χ(b ≥ 1)] + [χ(a ≥ 1) + χ(b ≥ 1)
+χ(a ≥ 1)χ(b ≥ 1)] + [χ(a = 1) + χ(b = 1) + χ(c = 1)]
+χ(b ≥ 1, c = 0),

which is U after simplifying.

For those c_{n} (mod 64) with ω_{2}(c_{n}) = 2, we can simply plug u_{16}(c_{n}) given in (47) into (32). Here we also show a precise classification by tables.

Theorem 6.3. Let n ∈ ℕ with d(α) = 2. Then we have

c_{n} ≡_{64} (−1)^{zr(α)}4 × 5^{u_{16}(CF_{2}(c_{n}))},

where u_{16}(CF_{2}(c_{n})) is given in (47). Precisely, let [α]_{2} = ⟨10^{a}10^{b}⟩_{2}, i.e., [n]_{2} = ⟨10^{a}10^{b+1}1^{β}⟩_{2}, and then we have c_{n} (mod 64) shown in the following four tables.

\begin{aligned}a = 0 & a = 1 & a = 2 & a ≥ 3 \\ b = 0 & 4 & 28 & 44 & 12 \\ b = 1 & 12 & 36 & 52 & 20 \\ b = 2 & 60 & 20 & 36 & 4 \\ b ≥ 3 & 28 & 52 & 4 & 36 \\ & when β = 0 \end{aligned}  \begin{aligned}a = 0 & a = 1 & a = 2 & a ≥ 3 \\ b = 0 & 52 & 12 & 28 & 60 \\ b = 1 & 44 & 4 & 20 & 52 \\ b = 2 & 60 & 20 & 36 & 4 \\ b ≥ 3 & 28 & 52 & 4 & 36 \\ & when β = 1 \end{aligned}

\begin{aligned}a = 0 & a = 1 & a = 2 & a ≥ 3 \\ b = 0 & 36 & 28 & 44 & 12 \\ b = 1 & 28 & 20 & 36 & 4 \\ b = 2 & 44 & 36 & 52 & 20 \\ b ≥ 3 & 12 & 4 & 20 & 52 \\ & when β = 2 \end{aligned}  \begin{aligned}a = 0 & a = 1 & a = 2 & a ≥ 3 \\ b = 0 & 4 & 60 & 12 & 44 \\ b = 1 & 60 & 52 & 4 & 36 \\ b = 2 & 12 & 4 & 20 & 52 \\ b ≥ 3 & 44 & 36 & 52 & 20 \\ & when β ≥ 3 \end{aligned}

Proof. Notice that there are difference between a ≥ 3 and a = 3, and similarly for b and β. We split (47) into two parts as follows:

A := χ(β′ = 0)(2α̈_{1} − α̈_{0} − 1) − χ(β′ = 1) + 2χ(β′ = 2)α̈_{0} + 2χ(β′ = 3)(1 − α̈_{0}),
B := 2[c_{2}(α̈) + α̈_{0}(1 − α̈_{2}) + #(S_{4}(α̈), {⟨0011⟩_{2}, ⟨1x00⟩_{2}})] − r_{1}(α̈) − zr_{1}(α̈)
+α̈_{0}α̈_{1} + 1.

Clearly, B is independent on β′. 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 β = 0 and B as follows:

a = 0 a = 1 a = 2 a = 3
b = 0 0  2  2  2
b = 1 1  1  1  1
b = 2 3  3  3  3
b = 3 3  3  3  3

value of A when β = 0

\begin{aligned}a = 0 & a = 1 & a = 2 & a = 3 \\ b = 0 & 0 & 2 & 1 & 3 \\ b = 1 & 0 & 1 & 2 & 0 \\ b = 2 & 3 & 2 & 3 & 1 \\ b = 3 & 1 & 0 & 1 & 3 \\ & value of B \end{aligned}

These two tables contribute u. Since we also know b(CF_{2}(c_{n})) ≡_{2} zr(α) = χ(a ≥ 1) + χ(b ≥ 1), we obtain (b, u) as follows:

a = 0 a = 1 a = 2 a = 3
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)

Now refer to the isomorphism ℤ_{16}^{∗} ≅ C_{2}×C_{4} in Table 1 to obtain the corresponding numbers, and then multiply each of them by 4 to justify the first table of this theorem.

Remark. 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} ≢_{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 ℤ_{32}^{∗} ≅ C_{2} × C_{8} in Table 1 as follows:

\begin{matrix}t ∈ ℤ_{32}^{∗} & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 & 25 & 27 & 29 & 31 \\ u_{32}(t) ∈ C_{8} & 7 & 1 & 6 & 6 & 1 & 7 & 0 & 4 & 3 & 5 & 2 & 2 & 5 & 3 & 4 \\ ∑_{s∈[3,t]_{o}} u_{32}(s) (mod 8) & 7 & 0 & 6 & 4 & 5 & 4 & 4 & 0 & 3 & 0 & 2 & 4 & 1 & 4 & 0 \end{matrix}

So we have

u_{32}(CF_{2}(n!)) ≡_{8} #(S_{5}(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},
23^{2}, 24^{2}, 25^{4}, 26^{4}, 27, 28, 29^{4}, 30^{4}})  (49)
=: ϕ_{32}(S_{5}(n̈)).

In this formula, n̈ can be replaced by n, ṅ or n̄. Unlike our operation from (39) to (43), 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 ϕ_{32}(S_{5}(n̈)) to be the right hand side of (49), in order to plug into ϕ_{32} with some other multi-sets instead of S_{5}(n̈). In the following, we set ϕ_{32}({[t]_{2}}) := ϕ_{32}({t}) for convenience.

u_{32}(CF_{2}(c_{n})) ≡_{8} ϕ_{32}(S_{5}(2n̈)) − 2ϕ_{32}(S_{5}(n̈)) − u_{32}(CF_{2}(n̄ + 1))
≡_{8} ϕ_{32}({⟨n̈_{3}n̈_{2}n̈_{1}n̈_{0}0⟩_{2}}) − ϕ_{32}(S_{5}(n̈)) − u_{32}(⟨α̈_{3}α̈_{2}α̈_{1}α̈_{0}1⟩_{2}). (50)

By this formula, we can classify c_{n} (mod 64) for those n with d(α) = 1 as follows:

Theorem 6.4. Let n ∈ ℕ with d(α) = 1. The congruences of c_{n} (mod 64) are classified by the following table.

α = 1 α = 2 α = 2^{2} α = 2^{3} α = 2^{s}
β = 0 2  14  22  38  6
β = 1 42  62  54  38  6
β = 2 34  22  14  62  30
β = 3 18  6  62  46  14
β ≥ 4 50  38  30  14  46

where s ≥ 4.

Proof. Adopt [α̈]_{2} and ⟨1^{β′}⟩_{2} as the two principal segments of [n̄]_{2} for k = 5 (not 6). We shall have d(α̈) = d(α) = 1 and β′ = min{β, 5}. We use (31) and (50) to obtain the next table for (b(CF_{2}(c_{n})), u_{32}(CF_{2}(c_{n}))) as follows:

α̈ = 1 α̈ = 2 α̈ = 2^{2} α̈ = 2^{3} α̈ = 2^{4}
β′ = 0 (0, 0) (1, 6) (1, 1) (1, 3) (1, 7)
β′ = 1 (0, 5) (1, 4) (1, 5) (1, 3) (1, 7)
β′ = 2 (0, 4) (1, 1) (1, 6) (1, 4) (1, 0)
β′ = 3 (0, 6) (1, 7) (1, 4) (1, 2) (1, 6)
β′ = 4 (0, 2) (1, 3) (1, 0) (1, 6) (1, 2)

Now find every corresponding number by referring to the isomorphism ℤ_{32}^{∗} ≅ C_{2} × C_{16} in Table 1, and then multiply the number by 2 to obtain the table in this theorem.

Corollary 6.5. We have c_{n} ≢_{64} 10, 26 and 58.

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 ∑_{t∈[3,s]_{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:

u_{64}(CF_{2}(n!)) ≡_{16} #(S_{6}(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},

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},

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},
51^{15}, 52^{15}, 53^{4}, 54^{4}, 55^{2}, 56^{2}, 57^{12}, 58^{12}, 59^{5}, 60^{5}, 61^{8}, 62^{8}})  (51)
=: ϕ_{64}(S_{6}(n̈));
u_{64}(CF_{2}(c_{n})) ≡_{16} ϕ_{64}(S_{6}(2n̈)) − 2ϕ_{64}(S_{6}(n̈)) − u_{64}(CF_{2}(n̄ + 1))
≡_{16} ϕ_{64}({⟨n̈_{4}n̈_{3}n̈_{2}n̈_{1}n̈_{0}0⟩_{2}}) − ϕ_{64}(S_{6}(n̈)) − u_{64}(⟨α̈_{4}α̈_{3}α̈_{2}α̈_{1}α̈_{0}1⟩_{2}).  (52)

The following theorem is directly checked by (52); so we skip its proof. On the other hand, by Theorem 5.2, we can verify this theorem by only enumerating c_{0}, c_{1}, c_{3}, c_{7}, c_{15}, and c_{31} (mod 64).

Theorem 6.6. Let n ∈ ℕ with d(α) = 0, i.e. n = 2^{β} − 1. Then we have

c_{n} ≡_{64} \{ \begin{matrix}1 if & β = 0 or 1; \\ 5 if & β = 2; \\ 45 if & β = 3; \\ 61 if & β = 4; \\ 29 if & β ≥ 5. \end{matrix}

Moreover, any number in [0, 63]_{o} − {1, 5, 29, 45, 61} can never be the congruence of c_{n} (mod 64).

7 Future research and acknowledgements

The odd congruences of c_{n} (mod 2^{k}) happen if and only if n = 2^{m} − 1 for m ∈ ℕ. 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 [15].

Theorem 7.1. Let k ≥ 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, …, k − 1.

In other words, if n = 2^{m} − 1 then c_{n} (mod 2^{k}) are distinct odd integers for m = 1, 2, …, k − 1. Associated with this theorem, there are a trivial fact c_{0} ≡_{2^{k}} c_{1} ≡_{2^{k}} 1 and a non-trivial fact c_{2^{m}−1} ≡_{2^{k}} c_{2^{k−1}−1} for each m ≥ k that directly follows Theorem 5.2.

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

(a) The congruences of c_{n} (mod p^{k}) for some odd prime p, which is a continuation of the work of this paper;

(b) The congruences of some other combinatorial numbers modulo a prime power, in particular, \binom{m}{n} and Motzkin numbers;

(c) A more efficient isomorphic machine exchanging between ℤ_{q^{k}}^{∗} and the corresponding additive group, in order to facilitate the arguments of this paper;

(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.

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.

References

[1] R. Alter and K. K. Kubota, Prime and prime power divisibility of Catalan numbers, J. Combin. Theory Ser. A 15 (1973), 243–256.

[2] K. S. Davis and W. A. Webb, Lucas’ theorem for prime powers, European J. Combin. 11 (1990), 229–233.

[3] K. S. Davis and W. A. Webb, Pascal’s triangle modulo 4, Fibonacci Quart. 29 (1991), 79–83.

[4] E. Deutsch and B. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory 117 (2006), 191–215.

[5] L. E. Dickson, History of the Theory of Numbers, Vol. I, Chelsea, 1919 (Chapter XI).

[6] R. Donaghey and L. W. Shapiro, Motzkin Numbers, J. Combin. Theory Ser. A 23 (1977), 291–301.

[7] S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. 116 (2006), 135–144.

[8] S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, Catalan and Motzkin numbers modulo 4 and 8, European J. Combin. 29 (2008), 1449–1466.

[9] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589–592.

[10] I. M. Gessel, Some congruences for Apéry numbers, J. Number Theory 14 (1982), 362– 368.

[11] A. Granville, Arithmetic properties of binomial coefficients I: binomial coefficients modulo prime powers, available at

http://www.cecm.sfu.ca/organics/papers/granville/index.html .

[12] A. Granville, Zaphod Beeblebrox’s brain and the fifty-ninth row of Pascal’s Triangle, Amer. Math. Monthly 99 (1992), 318–381.

[13] J. G. Huard, B. K. Spearman, and K. S. Williams, Pascal’s triangle (mod 8), European J. Combin. 19 (1998), 45–62.

[14] E. E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93–146.

[15] H.-Y. Lin, Odd Catalan numbers modulo 2^{k}, to appear in European J. Combin.

[16] F. Luca and M. Klazar, On integrality and periodicity of the Motzkin numbers, Aequ. Math. 69 (2005), 68–75.

[17] E. Lucas, Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques suivant un module premier, Bull. Soc. Math. France 6 (1878), 49–54.

[18] Y. Mimura, Congruence properties of Apery numbers, J. Number Theory 16 (1983), 138–146.

[19] A. Postnikov and B. Sagan, Note: What power of two divides a weighted Catalan number, J. Combin. Theory Ser. A 114 (2007), 970–977.

[20] H. Riesel, Prime Numbers and Computer Methods for Factorization, Springer, 1994.

[21] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[22] S. Wolfram, A New Kind of Science, Wolfram Media, 2002.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 11B50. Keywords: prime power modulus, Catalan numbers, Kummer’s theorem, Lucas’ theorem.

Received January 14 2010; revised version received April 30 2010. Published in Journal of Integer Sequences, May 3 2010.

Return to Journal of Integer Sequences home page.