1.9. COUNTING
i
“bookmt” — 2006/8/8 — 12:58 — page 55 — #67
i
i
1.9. COUNTING
55
1.8.14.
(a) Develop an algorithm to compute g:c:d.f1; f2; : : : ; fk/.
(b) Develop a computer program to compute the greatest common divisor of any finite collection of nonzero polynomials with real coefficients.
1.8.15.
(a) Suppose that p.x/ D anxn C C a1x C a0 2 ZŒx. Suppose that r=s 2 Q is a root of p, where r and s are relatively prime integers. Show that s divides an and r divides a0. Hint: Start with the equation p.r=s/ D 0, multiply by sn, and note, for example, that all the terms except anrn are divisible by s.
(b) Conclude that any rational root of a monic polynomial in ZŒx is an integer.
p
(c) Conclude that x2 2 has no rational root, and therefore 2 is irrational.
1.8.16.
(a) Show that a quadratic or cubic polynomial f .x/ in KŒx is irreducible if, and only if, f .x/ has no root in K.
(b) A monic quadratic or cubic polynomial f .x/ 2 ZŒx is irreducible if, and only if, it has no integer root.
(c)
x3 3x C 1 is irreducible in QŒx.
1.9. Counting Counting is a fundamental and pervasive technique in algebra. In this section we will discuss two basic counting tools, the binomial coefficients and the method of inclusion-exclusion. These tools will be used to establish some not at all obvious results in number theory: First, the binomial coefficients and the binomial theorem are used to prove Fermat’s little theorem (Proposition 1.9.10); then inclusion –exclusion is used to obtain a formula for the Euler ' function (Proposition 1.9.18). Finally, we use the formula for the ' function to obtain Euler’s generalization of the little Fermat theorem (Theorem 1.9.20).
Let’s begin with some problems on counting subsets of a set. How many subsets are there of the set f1; 2; 3g? There are 8 D 23 subsets, namely ;, f1g, f2g, f3g, f1; 2g, f1; 3g, f2; 3g, and f1; 2; 3g.
How many subsets are there of a set with n elements? For each of the n elements we have two possibilities: The element is in the subset, or not. The in/out choices for the n elements are independent, so there are 2n possibilities, that is, 2n subsets of a set with n elements.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 56 — #68
i
i
56
1. ALGEBRAIC THEMES
Here is another way to see this: Define a map from the set of subsets of f1; 2; : : : ; ng to the set of sequences .s1; s2; : : : ; sn/ with each si 2 f0; 1g. Given a subset A of f1; 2; : : : ; ng, form the corresponding sequence .A/ by putting a 1 in the j th position if j 2 A and a 0 in the j th position otherwise. It’s not hard to check that is a bijection. Therefore, there are just as many subsets of f1; 2; : : : ; ng as there are sequences of n 0’s and 1’s, namely 2n.
Proposition 1.9.1. A set with n elements has 2n subsets.
How many two–element subsets are there of a set with five elements?
You can list all the two–element subsets of f1; 2; : : : ; 5g and find that there are 10 of them.
How many two–element subsets are there of a set with n elements?
n
Let’s denote the number of two–element subsets by . A two–element
2
subset of f1; 2; : : : ; ng either includes n or not. There are n 1 two– element subsets that do include n, since there are n 1 choices for the second element, and the number of two–element subsets that do not in n
1
clude n is . Thus, we have the recursive relation
2
n
n
1
D .n
1/ C :
2
2
For example,
5
4
3
D 4 C
D 4 C 3 C
2
2
2
2
D 4 C 3 C 2 C D 4 C 3 C 2 C 1 D 10:
2
In general, n D .n 1/ C .n 2/ C C 2 C 1:
2
This sum is well known and equal to n.n 1/=2. (You can find an inductive proof of the formula
.n
1/ C .n
2/ C C 2 C 1 D n.n
1/=2
in Appendix C.1.)
Here is another argument for the formula n D n.n 1/=2
2
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 57 — #69
i
i
1.9. COUNTING
57
that is better because it generalizes. Think of building the nŠ permutations of f1; 2; : : : ; ng in the following way. First choose two elements to be the n
first two (leaving n 2 to be the last n 2). This can be done in ways.
2
Then arrange the first 2 (in 2Š D 2 ways) and the last n 2 (in .n
2/Š
ways). This strange process for building permutations gives the formula
n
nŠ D
2Š .n
2/Š :
2
Now dividing by 2Š .n 2/Š gives
n
nŠ
n.n
1/
D
D
:
2
2Š.n
2/Š
2
The virtue of this argument is that it remains valid if 2 is replaced by any k, 0 k n. So we have the following:
Proposition 1.9.2. Let n be a natural number and let k be an integer in
n the range 0 k n. Let denote the number of k-element subsets of
k an n-element set. Then
n
nŠ
D
:
k
kŠ.n
k/Š
n
We extend the definition by declaring D 0 if k is negative or
k
0
0
greater than n. Also, we declare D 1 and D 0 if k ¤ 0. Note
0
k
n
n
n that
D
D 1 for all n 0. The expression is generally read
0
n
k
as “n choose k.”
n
Here are some elementary properties of the numbers .
k
Lemma 1.9.3. Let n be a natural number and k 2 Z.
n (a) is a nonnegative integer.
k
n
n
(b)
D .
k
n
k
n
n
1
n
1
(c)
D
C
.
k
k
k
1
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 58 — #70
i
i
58
1. ALGEBRAIC THEMES
n
Proof. Part (a) is evident from the definition of .
k
n
nŠ
The formula
D implies (b) when 0 k n. But
k
kŠ.n
k/Š
when k is not in this range, neither is n k, so both sides of (b) are zero.
When k is 0, both sides of (c) are equal to 1. When k is negative or greater than n, both sides of (c) are zero. For 0