Fall 2007

**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.