7.5 MISCELLANEOUS INSTRUCTIVE EXAMPLES 249If You Can Count It, It's an Integer
Example 7.5.2 Let kEN. Show that the product of k consecutive integers is divisible
by k!.
Solution: It is possible to solve this problem with "pure" number theoretic rea
soning, but it is far simpler and much more enjoyable to simply observe that
m(m+l)(m+2)···(m +k-l)
=
(m+k-l)k! k '
and binomial coefficients are integers! •
The moral of the story: Keep your point of view flexible. Anything involving
integers is fair game for combinatorial reasoning. The next example continues this
idea.
A Combinatorial Proof of Fermat's Little Theorem
Recall that Fermat's little theorem (page 232) states that if p is prime, then
aP == a (modp)
holds for all a. Equivalently, FLT says that aP - a is a multiple of p. The expression
aP has many simple combinatorial interpretations. For example, there are aP different
p-Ietter words possible using an alphabet of a letters.
Let's take the example of a = 26, p = 7, and consider the "dictionary" � of these
267 words. Define the shift function s : � ---* � to be the operation that moves the last
(rightmost) letter of a word to the beginning position. For example, s( fermats) =
sfermat. We will call two words in � "sisters" if it is possible to transform one into
the other with finitely many applications of the shift function. For example, integer
and gerinte are sisters, since s^3 (integer) = gerinte. Let us call all of the
sisters of a word its "sorority." Since any word is its own sister, the sorority containing
integer consists of this word and
rintege, erinteg, gerinte, egerint, tegerin, ntegeri.
7.5.3 Show that if s(U) = U, then U is a word all of whose letters are the same. There
are of course exactly 26 such "boring" words,
aaaaaaa, bbbbbbb, ... , z z z z z z z.7.5.4 Show additionally that if sr(u) = U where 0 < r < 7, then U must be a boring
word.
7.5.5 Show that all sororities have either one member or exactly seven members.
7.5.6 Conclude that the 267 - 26 non-boring words in � must be a multiple of 7.
7.5.7 Finally, generalize your argument so that it works for any prime p. What simple
number theory principle is needed to carry out the proof?