RESIDUES OF GENERALIZED BINOMIAL



RESIDUES OF GENERALIZED BINOMIAL

COEFFICIENTS MODULO A PRODUCT OF PRIMES

Erik R. Tou

Honors Mathematics Thesis

Department of Mathematics and Computer Science

Gustavus Adolphus College

St. Peter, MN

Spring 2002

Abstract. Take a sequence [pic] of positive integers generated by [pic], [pic], [pic] ([pic]). For [pic], [pic] becomes the familiar Fibonacci sequence. From this sequence, one may define the generalized factorial [pic] and the generalized binomial coefficient [pic][pic]. The residues of these coefficients modulo a prime have a number of well-documented properties, including a remarkable self-similarity. While the result is more complicated when these coefficients are reduced by product [pic] of primes, some of the modulo p properties are inherited in the modulo [pic] case.

1. Introduction

Define the binomial coefficient [pic] as

[pic].

A theorem of E. Lucas [5] gives a way to determine the residue of a binomial coefficient modulo a prime p in terms of the base-p digits of m and n. If [pic] and [pic], where [pic], then

[pic] [pic].

This theorem also allows for considerable flexibility in the evaluation of the congruence. For example, given any positive integer [pic],

[pic]

[pic]

[pic],

where [pic] is the integer quotient of m by [pic], and [pic] is the remainder. A generalized binomial coefficient corresponds to a particular sequence [pic], with which [pic] is replaced by the product [pic]. When [pic] is a second-order recursive sequence, a more limited version of Lucas’ theorem will hold.

In both cases, the array of residues has a self-similar structure modulo p. The situation modulo a product [pic] of primes is more complex, and possesses fewer of the properties of the binomial and generalized binomial coefficients modulo p. However, some of these properties do translate from primes to products of primes, which [pic] inherits from its prime factors.

2. Some Results Regarding the General Fibonacci Sequence [pic]

Definition 1. Let [pic], and let p be any prime. The sequence [pic] is defined recursively as [pic], [pic], and [pic][pic] for [pic].

In the case [pic], [pic] is the Fibonacci sequence. When [pic] and [pic], [pic] is the sequence of non-negative integers.

Definition 2. Let r denote the rank of apparition of p in the sequence [pic]; that is, [pic]. Let [pic] denote the least period of the sequence [pic] of residues, if it exists. Let [pic].

Throughout this paper, consider the prime p and the integers a and b to be fixed, and assume that a and b are not both zero.

Recall that there exists a closed form for the generalized Fibonacci sequence. Let [pic] and [pic] be the roots of the quadratic equation [pic]. That is, let [pic] and [pic]. Then, for any [pic], [pic]. For convenience, we denote [pic]. In the case that [pic], the closed form is [pic]. With this description, we can extend a number of well-known identities of Fibonacci numbers to the more general case.

Lemma 1. For [pic],

[pic],

where [pic] represents the greatest integer less than or equal to [pic].

Proof. The proof of this identity consists largely of an algebraic manipulation of the closed form already given. Expanding [pic] and [pic], we have

[pic][pic].

Using the binomial theorem on the [pic] and [pic] terms, this equation may be further expanded, as follows:

[pic]

[pic].

In the second of the two summations, i is even, and so [pic]. Thus, the entire sum reduces to zero as well. In the first summation, [pic]. With this fact, and a simple re-indexing, the expression becomes

[pic]

[pic],

where [pic] represents the greatest integer less than or equal to [pic]. □

Lemma 2. For [pic], [pic].

Proof. First, suppose that [pic]. Then [pic], and using the closed form [pic], we have

[pic]

[pic]

[pic]

[pic].

Next, suppose [pic]. Then, the closed form is [pic], and we use the following identity:

[pic][pic]

[pic][pic].

With this, the identity will follow from direct algebraic manipulation:

[pic][pic]

[pic]

[pic]

[pic]

[pic]

[pic][pic]. □

At this point, a theorem of Fermat’s is stated for future reference, and will be used frequently from here on.

Theorem 1. (Fermat) Let p be any prime, and let a be any integer. If p does not divide a, then [pic] [pic]. Equivalently, we have [pic] [pic].

Lemma 3. Let p be any prime. If p does not divide b, then p divides at least one of [pic], [pic], and [pic].

Proof. First, suppose that [pic]. Then, [pic] and [pic]. If a is even, then [pic]. If a is odd, then since 2 does not divide b (by hypothesis), [pic] [pic]. Thus, [pic]. And so, the lemma holds for the case [pic].

Next, let p be an odd prime and suppose that [pic]. Then, [pic] and Fermat’s theorem may be applied in conjunction with Lemma 1 to get

[pic]

[pic] [pic].

Recall that for [pic], [pic] [pic]; as a result, this sum reduces to

[pic]

[pic] [pic].

By assumption, [pic]. Thus, [pic].

Lastly, suppose that p is an odd prime but that p does not divide [pic]. Using Lemma 2 and the previous case in this lemma,

[pic][pic][pic] [pic].

Since p divides neither [pic] nor [pic], Fermat’s theorem tells us that

[pic] [pic].

Hence, p divides at least one of [pic] and [pic]. In general, then, if p does not divide b, then p must divide at least one of [pic], [pic], and [pic]. □

Corollary 1. If p does not divide b, then [pic].

Corollary 2. Suppose that the following statements hold:

(1) [pic] are primes, with [pic],

(2) it is not the case that [pic] and [pic],

(3) [pic] does not divide b.

Then, if there exist non-negative integers [pic] such that [pic] [pic], we must have [pic] for all [pic].

Proof. For [pic], since [pic] and [pic], it follows that [pic]. That is, there exists a positive integer v such that [pic]. By Corollary 1 above, [pic]. This results in the following:

[pic].

Therefore, [pic]. □

Also, note that if [pic] and [pic], the same argument may be applied to give [pic] for [pic].

3. Generalized Binomial Coefficients Modulo p

Definition 3. Given a generalized Fibonacci sequence and a non-negative integer n, define the bracket factorial as [pic], with [pic]. Then, for any pair [pic] of non-negative integers, the generalized binomial coefficient is defined as

[pic].

If any factors are zero, then the zeroes in the numerator and denominator are to be cancelled in pairs. A result by Holte [3] guarantees that the number of zero factors in the numerator will either be one greater than the number of factors in the denominator or will be exactly equal.

Definition 4. A prime p is said to be ideal for the sequence [pic] if [pic] for all positive integers k.

Lemma 4. Let p be an ideal prime for the sequence [pic], and let [pic]. Suppose that for some [pic], [pic] and [pic], where m' and n' are non-negative integers, and [pic]. Then, [pic] implies

[pic] [pic] [pic].

Proof. As proven in [4] and treated in [2], the number of times that p divides [pic] is the number of carries that occur when m and n are added in the mixed-radix system with radices [pic], [pic], [pic] , etc. So, consider the addition [pic] in such a manner. We have the following:

k [pic] [pic] [pic] … 3 2 1 0

[pic] [pic] [pic] [pic] … [pic] [pic] r 1

[pic] p p p … p p r *

Carries c -- -- … -- -- -- --

[pic] Augend 0 [pic] [pic] … [pic] [pic] [pic] [pic]

+ [pic] Addend 0 [pic] [pic] … [pic] [pic] [pic] [pic]

[pic] Sum [pic] [pic] [pic] … [pic] [pic] [pic] [pic]

Since [pic] and [pic], we know that by the above adding scheme, [pic], and hence [pic]. And so, if we add [pic] and [pic] by the same method, there will be at least one carry from the [pic]th column to the [pic]st column, because of i and j. There may be other carries before or after this one, but such an occurrence is not necessary. This one carry guarantees that p will divide [pic] at least once. Therefore, [pic] [pic]. □

In simpler terms, Lemma 4 says that if a particular [pic] value lies in the lower right triangle of a matrix of coefficients, with dimension [pic] ([pic]), then it is a multiple of p.

Theorem 2. ([pic]-step recurrence modulo p) If p does not divide b, and p is an ideal prime for the sequence [pic], we have that for any [pic] and for all [pic],

[pic] [pic].

Proof. (by induction on [pic]) First, let [pic]. Then for all [pic], the congruence reduces to

[pic],

which is proven in [3]. Next, consider an arbitrary [pic], and suppose that our congruence holds for all [pic] and all [pic]. Then,

[pic].

Applying the inductive hypothesis, we have that

[pic]

[pic] ([pic])

[pic] [pic].

By Corollaries 1 and 3 in [3], we know that for any positive integer k, [pic] [pic]. Thus, Fermat’s theorem tells us that [pic] [pic]. As a result, ([pic]) reduces to

[pic]

[pic] ([pic])

[pic] [pic].

The method here is to apply the inductive hypothesis to the above equation, ultimately repeating the process p times. Applying the inductive hypothesis to ([pic]), we have

[pic]

[pic] (1)

[pic] (2)

[pic] (3)

[pic] (4)

The general binomial coefficient in expressions (2) and (3) can rewritten as

[pic].

Since [pic], Lemma 4 dictates that [pic] [pic], and hence the entire expression reduces to

[pic] (5)

[pic]. (6)

When this process is repeated with (5) and (6), the result will have expressions of the forms (1), (2), (3), and (4). Each time, the expressions corresponding to (2) and (3) will be congruent to zero modulo p. To see this, consider an arbitrary ith iteration of this process ([pic]); the general binomial coefficient corresponding to that in expression (2) will be as follows:

[pic]

[pic].

Again, [pic] (as long as [pic]), whence Lemma 4 tells us that this coefficient is congruent to zero modulo p. A similar method will demonstrate the same result for the general binomial coefficient that corresponds to that in expression (3) of the ith iteration. Hence, if we apply the inductive hypothesis p times to ([pic]), we will accumulate factors of the form [pic]and [pic] in front of the general binomial coefficients in the corresponding expressions (1) and (4), respectively, giving us the following:

[pic]

[pic] (7)

[pic]

Simplification yields the following result:

[pic] [pic].

Again using Fermat’s theorem, we have that [pic] [pic]. Hence, expression (7) may be further simplified to get

[pic] [pic]. □

Example 1: Fibonomial Coefficients Modulo 2 and 3. Using the Fibonacci sequence, with [pic]or 3, and [pic], [pic] [pic]. To see this, first take [pic]. Then, applying Theorem 2 with [pic] and [pic], we have the following:

[pic]

[pic].

Since [pic] [pic], this reduces to

[pic].

For [pic], note that [pic] [pic]; applying Theorem 2 with [pic] and [pic] will similarly yield [pic] [pic].

Example 2: Fibonomial Coefficients Modulo 6. Using the Fibonacci sequence, and given [pic], [pic][pic] [pic]. For simplicity, we use the following notation: [pic]; [pic]; [pic]. Under this notation system, we want to show that [pic] [pic]. As seen in Example 1, [pic] [pic] and [pic] [pic]. That is, the integer [pic] is a multiple of both 2 and 3. This means that [pic] is also a multiple of 6, which ultimately tells us that [pic] [pic]. Or, using the original notation, [pic][pic] [pic].

4. Generalized Binomial Coefficients Modulo a Product of Primes

Given the considerable body of knowledge concerning the generalized binomial coefficients modulo a prime, the natural tendency when considering these coefficients modulo a product of primes is to extend previous knowledge (to what extent it is possible) to this more general case. If one is given the residues of a particular [pic] value modulo primes [pic], the most direct way to find the residue value modulo [pic] is to make use of the Chinese Remainder Theorem, which is restated here.

The Chinese Remainder Theorem.[1] Let [pic] denote k positive integers that are relatively prime in pairs, and let [pic] denote any k integers. Then the congruences [pic], [pic], have common solutions. Any two solutions are congruent modulo [pic].

Fortunately, the Chinese Remainder Theorem is constructive. By defining [pic] to be the solution to the congruence [pic] [pic], [pic], the common solution is

[pic].

Corollary. Given primes [pic] such that [pic], let [pic]. Let [pic] be the solution to the congruence relation [pic] [pic], for each [pic]. Lastly, taking [pic], let [pic]. Then,

[pic][pic].

Proof. This follows directly from the proof of the theorem, and in particular the definition of [pic]. Here, we take [pic] and [pic] for each [pic]. Then, the theorem gives [pic] as the common solution, where the [pic] are defined as the solutions to the congruences stated above. Thus, for any [pic],

[pic][pic][pic][pic][pic].

That is, [pic] [pic] for each [pic]. Therefore, [pic] [pic]. □

Definition 5. Given primes [pic], ([pic]), we can use the corollary above to construct an operator [pic], for which [pic][pic]. Note that when [pic] ([pic]), [pic] reduces to the congruence relation given by the corollary; that is, [pic] [pic].

Lemma 5. Suppose that for integers [pic], [pic] [pic] for each [pic]. Then, [pic] [pic].

Proof. Let [pic] be as described above. Then,

[pic]

[pic]

[pic].

Since [pic] [pic], the integer [pic] is a multiple of [pic], for each [pic]. And since [pic] is a multiple of all the primes except [pic], each term in the summation above is a multiple of [pic]. Hence, [pic] [pic]. Recall that by definition, [pic] [pic] [pic]. Therefore, [pic][pic] [pic] [pic]. □

Lemma 6. Suppose that for integers [pic], there exists an integer a such that [pic] for each [pic]. Further suppose that [pic] [pic]. Then, [pic] [pic] [pic].

Proof. Using Lemma 5, we have the following chain of congruences:

[pic]

[pic][pic]

[pic] [pic]. □

Definition 6. We may also extend the function [pic] to a matrix operation. Given matrices [pic] of dimensions d [pic] d, define [pic] componentwise; that is, [pic][pic], [pic].

Notation. Let m be a non-negative integer. For any prime [pic] and any positive integer [pic], define the following:

[pic] [pic] [pic]the least period of [pic]

[pic] [pic]

[pic] [pic]

[pic]

Theorem 3. (Holte) If [pic] does not divide b, then for [pic],

[pic] [pic],

where [pic] is an r [pic]r matrix determined by the values [pic] and [pic], as described in [3].

Furthermore, we will use the convention [pic], where [pic] and [pic] are any pair of non-negative integers. Since [pic], this means that [pic] [pic].

Definition 7. Given a prime [pic], let [pic] denote the associated [pic] matrix determined by the values [pic] and [pic], as described in Theorem 3. Then, given any non-negative integer [pic], define

[pic] [pic], [pic].

Note that [pic] has dimensions [pic], and that [pic][pic]. Additionally, given any pair [pic],[pic] of non-negative integers, [pic], we denote the [pic],[pic]entry of the matrix [pic] as

[pic].

With this we may restate Theorem 3 under a modified system of notation: if [pic] does not divide b, then, for [pic], [pic] [pic].

Definition 8. For any non-negative integer m, any prime [pic], and any non-negative integer [pic], define [pic] and [pic]. Note that if [pic], [pic].

Theorem 4. Let [pic] be primes, with [pic], and let [pic]. Suppose there exist non-negative integers [pic] such that [pic] [pic] (denote this value [pic]). If for each [pic], [pic] does not divide b, then for [pic],

[pic] [pic],

where

[pic].

Also, if it is not the case that [pic] and [pic], then [pic] as well.

Proof. Let [pic] be an arbitrary prime, and suppose that [pic]. Then, Theorem 3 tells us that

[pic] [pic]. (1)

Now, recall that we have assumed there exist non-negative integers [pic] such that [pic]. Applying Lucas’s theorem to the binomial term, we have that

[pic][pic]

[pic] [pic] [pic].

Along with expression (1) above, this gives us

[pic] [pic].

Expanding the notation, the last two factors of this expression become

[pic]

[pic] (2)

[pic] [pic].

Next, we show that if [pic], [pic][pic]. This involves writing m in a mixed-radix system, as in Lemma 4. Taking m as [pic], we have that

[pic][pic]

[pic][pic]

[pic][pic]

[pic].

Making this substitution in (2), we get

[pic]

[pic].

By Definition 7, this is

[pic].

Hence, if [pic], [pic][pic][pic] [pic].

In the case [pic], we have the simplified relation [pic]. Thus, [pic], [pic], and Theorem 3 gives

[pic]

[pic]

[pic] [pic].

Furthermore, Corollary 2 to Lemma 3 tells us that for [pic], [pic]. For these values of i, we will write [pic]. Next, we use the matrix version of the operator [pic] in conjunction with Lemma 6 to conclude that

[pic][pic]

[pic] [pic],

or more simply,

[pic] [pic].

Additionally, if it is not the case that [pic] and [pic], then Corollary 2 tells us that [pic] as well. □

Example: Fibonomial Coefficients Modulo 6. Using the Fibonacci sequence, take [pic] and [pic]. Then, we have the relation [pic]; thus, [pic] and [pic]. A simple congruence is [pic] [pic] [pic]. A more complicated case is the coefficient [pic]. Here, [pic], and [pic]. Then,

[pic]

[pic]

[pic]

[pic][pic] [pic].

5. Open Questions

Modulo p, one may reduce the subscripts of the [pic] matrix modulo s. This reduction allows for a complete tabulation of the number of distinct matrices of this type. In the example above, we were able to derive the relation [pic]. Since [pic], the relation is really [pic]. In terms of the Fibonacci sequence, Halton [1] has proven that for any positive integer [pic], [pic]. A similar result holds for [pic]. A determination of [pic] in these terms would allow for a reduction of the subscripts of [pic] modulo s, and give a way to compute the precise number of distinct [pic] matrices. Modulo p, (where p does not divide b), Holte has found this number to be [pic]. Modulo [pic], we can at least say that the number of distinct non-zero [pic] matrices is no more than [pic].

Additionally, any similar results regarding powers of primes would allow the work done here to expand into the further realm of all positive integers, rather than simply a product of primes. Recall that the Chinese Remainder Theorem applies to a collection [pic] of positive integers that are relatively prime in pairs. If such a result does exist for powers of primes, it may be possible to extend Theorem 4 to include these cases as well.

In more general terms, a classification of all prime products with the [pic] [pic] relation would delineate the full applicability of the results for the product [pic].

References

[1] Halton, John H., On the Divisibility Properties of Fibonacci Numbers, Fibonacci Quart. 15 (Oct. 1966), 217-240.

[2] Holte, John M., Asymptotic Prime-power Divisibility of Binomial, Generalized Binomial, and Multinomial coefficients, Transactions of the American Mathematical Society. Vol. 349, No. 10 (Oct. 1997), 3837-3873.

[3] Holte, John M., Residues of Generalized Binomial Coefficients Modulo a Prime, Fibonacci Quart. 38 (June-July 2000), 227-238.

[4] Knuth, D. E. and H. S. Wilf, The Power of a Prime That Divides a Generalized Binomial Coefficient, J. reine angew. Math. 396 (1989), 212-219.

[5] Lucas, E., Théorie des functions numériques simplement périodiques, Amer. J. Math. 1 (1878), 184-240.

[6] Niven, Ivan, and Herbert S. Zuckerman. An Introduction to the Theory of Numbers, 3rd ed. New York: John Wiley & Sons, Inc., 1964.

-----------------------

[1] Given in [6], page 31. See the text for more details on this theorem and the Corollary to follow.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download