12 Chapter 2
Proof #6 (by modular arithmetic). Modular arithmetic, modulo 2, refers to the system of
arithmetic system that arises by replacing every integer with its residue modulo 2, or in
other words, with its remainder after dividing by 2. (More generally, one can carry out
modular arithmetic modulo any given base b > 1.) The main point of modular arithmetic
is that the arithmetic operations are indeed well defined on these residues. In modular
arithmetic modulo 2, residues are either 0 or 1, and so n
2
n mod 2 is either 0
2
0 = 0or
1
2
1 = 0, and in either case we get 0 mod 2, which means n
2
n is even.
Finally, we prove the theorem using the following summation identity, which the reader
may happen to know:
1 + 2 + ···+ (n 1) = n(n 1)/2.
This identity is important in the subject of finite combinatorics, since as we mentioned this
quantity is the number of ways of choosing two objects from a set of n objects. We shall
prove it in chapter 4 and again with a different proof in chapter 6.
Proof #7 (using summation identity). The point is that identity immediately implies that
n(n1)/2 is an integer, since the left side of the identity is an integer. And so the numerator
n(n 1) must be even, and therefore n
2
n is even.
Can you find any other proofs of theorem 6?
2.3 Different proofs suggest different generalizations
We had mentioned that mathematicians sometimes find it valuable to have multiple proofs
of a theorem, because the different proof ideas may emphasize different aspects of the
theorem, which may suggest different avenues for generalization. Even slightly different
but equivalent ways of stating a theorem could suggest different generalizations. How does
that play out here? Several of the arguments turned on the fact that n
2
n = n(n 1), and
so the two assertions
2 divides n(n 1),
2 divides n
2
n
are simply equivalent to each other. But perhaps these different ways of stating the result
already suggest different ways to generalize the statement.
For example, let us try to generalize the theorem by considering multiples of 3, rather
than 2. The two statements above perhaps suggest the following generalizations:
3 divides (n + 1)n(n 1), and
3 divides n
3
n.
These statements are actually equivalent to each other, as one can see by verifying that
(n + 1)n(n 1) = n(n
2
1) = n
3
n. Furthermore, the high-school-algebra proof above
generalizes to show that indeed the statements are true, since (n + 1)n(n 1) is the product