Chapter 1
Integers and Permutations
God made the integers, and all the rest is the work of man.
—Leopold Kronecker
The use of arithmetic is a basic aspect of human culture. Anthropologists tell us that even the most primitive societies, because of their desire to count objects, have developed some sort of terminology for the numbers 1, 2, and 3, although many go no further. As a culture develops, it needs more sophisticated counting to deal with commerce, warfare, the calendar, and so on. This leads to methods of recording numbers often (but by no means always) based on groups of 10, presumably from counting on the fingers. Then the recording of numbers by making marks or notches becomes important (in bookkeeping, for example), and a variety of systems have been constructed for doing so. Many of these systems were not very useful for adding or multiplying (try multiplying with Roman numerals), and the development of our positional system, originating with the Babylonians using base 60 rather than 10, was a great advance.
In this chapter we assume the validity of the elementary arithmetic properties of the integers and use them to derive some more subtle facts related to divisibility and primes. Then two fundamental algebraic systems are described: the integers modulo n and the permutations of the set {1, 2, . . ., n}. These are, respectively, excellent examples of rings and groups, two of the basic algebraic structures presented in detail in Chapters 2 and 3.
1.1 Induction
Great ...
