Algebra & Number Theory [1/01/2003]
A. Baker Department of Mathematics, University of Glasgow. E-mail address:
[email protected] URL: http://www.maths.gla.ac.uk/∼ajb
Contents Chapter 1. Basic Number Theory 1. The natural numbers 2. The integers 3. The Euclidean Algorithm and the method of back-substitution 4. The tabular method 5. Congruences 6. Primes and factorization 7. Congruences modulo a prime 8. Finite continued fractions 9. Infinite continued fractions 10. Diophantine equations 11. Pell’s equation Problem Set 1
1 1 3 4 6 8 11 13 16 17 22 24 26
Chapter 2. Groups and group actions 1. Groups 2. Permutation groups 3. The sign of a permutation 4. The cycle type of a permutation 5. Symmetry groups 6. Subgroups and Lagrange’s Theorem 7. Group actions Problem Set 2
29 29 30 31 32 33 35 38 43
Chapter 3. Arithmetic functions 1. Definition and examples of arithmetic functions 2. Convolution and M¨obius Inversion Problem Set 3
47 47 48 52
Chapter 4. Finite and infinite sets, cardinality and countability 1. Finite sets and cardinality 2. Infinite sets 3. Countable sets 4. Power sets and their cardinality 5. The real numbers are uncountable Problem Set 4
53 53 55 55 57 59 60
Index
61
1
CHAPTER 1
Basic Number Theory 1. The natural numbers The natural numbers 0, 1, 2, . . . form the most basic type of number and arise when counting elements of finite sets. We denote the set of all natural numbers by N0 = {0, 1, 2, 3, 4, . . .} and nowadays this is very standard notation. It is perhaps worth remarking that some people exclude 0 from the natural numbers but we will include it since the empty set ∅ has 0 elements! We will use the notation Z+ for the set of all positive natural numbers Z+ = {n ∈ N0 : n 6= 0} = {1, 2, 3, 4, . . .}, which is also often denoted N, although some authors also use this to denote our N0 . We can add and multiply natural numbers to obtain new ones, i.e., if a, b ∈ N0 , then a + b ∈ N0 and ab ∈ N0 . Of course we have the familiar properties of these operations such as a + b = b + a,
ab = ba,
a + 0 = a = 0 + a,
a1 = a = 1a,
a0 = 0 = 0a,
etc.
We can also compare natural numbers using inequalities. Given x, y ∈ N0 exactly one of the following must be true: x = y, x < y,="" y="">< x.="" as="" usual,="" if="" one="" of="" x="y" or="" x="">< y="" holds="" then="" we="" write="" x="" 6="" y="" or="" y=""> x. Inequality is transitive in the sense that x < y="" and="" y="">< z="⇒" x="">< z.="" the="" most="" subtle="" aspect="" of="" the="" natural="" numbers="" to="" deal="" with="" is="" the="" fact="" that="" they="" form="" an="" infinite="" set.="" we="" can="" and="" usually="" do="" list="" the="" elements="" of="" n0="" in="" the="" sequence="" 0,="" 1,="" 2,="" 3,="" 4,="" .="" .="" .="" which="" never="" ends.="" one="" of="" the="" most="" important="" properties="" of="" n0="" is="" the="" well="" ordering="" principle="" (wop):="" every="" non-empty="" subset="" s="" ⊆="" n0="" contains="" a="" least="" element.="" a="" least="" or="" minimal="" element="" of="" a="" subset="" s="" ⊆="" n0="" is="" an="" element="" s0="" ∈="" s="" for="" which="" s0="" 6="" s="" for="" all="" s="" ∈="" s.="" similarly,="" a="" greatest="" or="" maximal="" element="" of="" s="" is="" one="" for="" which="" s="" 6="" s0="" for="" all="" s="" ∈="" s.="" notice="" that="" n0="" has="" a="" least="" element="" 0,="" but="" has="" no="" greatest="" element="" since="" for="" each="" n="" ∈="" n0="" ,="" n="" +="" 1="" ∈="" n0="" and="" n="">< n="" +="" 1.="" it="" is="" easy="" to="" see="" that="" least="" and="" greatest="" elements="" (if="" they="" e