Summaries of lectures
These brief summaries of the material covered in each lecture will normally be posted about 5 days after the lecture.
9/5/07: (a) The set of integers (denoted Z) satisfies the Well-ordering Axiom: Every nonempty subset of the nonnegative integers contains a smallest element.
(b) Using the well-ordering axiom one can prove the Division Algorithm: Let a,b belong to Z, b > 0. Then there exist unique integers q and r such that
a = bq + r, 0 ≤ r < b.
(c) If a,b belong to Z, b ≠ 0, we say “b divides a” and write b│a if a = bt for some integer t. In this case we say that a is a factor of b or that a is a divisor of b.
(d) If a, b belong to Z we say that an integer c is a common divisor of a and b if c divides a and c divides b.
(e) If a, b belong to Z and are not both 0, we say that c is the greatest common divisor of a and b if c is a common divisor of a and b and if whenever d is a common divisor of a and b then c ≥ d. We frequently denote the greatest common divisor of a and b by (a,b).
(f) If a, b belong to Z and are not both 0, then (a,b) = ra + sb for some integers r and s and (a,b) is the smallest positive integer that can be expressed in this form. This is prove by letting S denote the set of all positive integers that can be written in the form ra + sb for some integers r and s. Then S is a nonempty set of nonnegative integers so it contains a smallest element, say d. Then every common divisor of a and b divides d (this is the easy part) and d is a common divisor of a and b (use the division algorithm to prove this).
(g) If a, b belong to Z and are not both 0 and (a,b) = 1, we say that a and b are relatively prime.
(h) If a divides bc and if (a,b) = 1, then a divides c. (To see this, use (f) to write 1 = ra + sb and then multiply both sides by c to get c = rac + sbc and note that both summands are divisible by a.
(i) We say that an integer p is prime if p ≠ 0, p ≠ ±1, and the only factors of p are ±1 and ±p. Note that according to this definition there are negative prime numbers (e.g., -5 is prime). This is unusual – most authors require that prime integers be positive.