文档介绍：page 1 of Chapter 0
Chapter 0 PREREQUISITES
All topics listed in this chapter are covered in A Primer of Abstract Mathematics by Robert
B. Ash, MAA 1998.
Elementary Number Theory
The mon divisor of two integers can be found by the Euclidean algorithm,
which is reviewed in the exercises in Section . Among the important consequences of the
algorithm are the following three results.
If d is the mon divisor of a and b, then there are integers s and t such
that sa + tb = d. In particular, if a and b are relatively prime, there are integers s and t
such that sa + tb =1.
If a prime p divides a product a1 ···an of integers, then p divides at least one ai
Unique Factorization Theorem If a is an integer, not 0 or ±1, then
(1) a can be written as a product p1 ···pn of primes.
(2) If a = p1 ···pn = q1 ···qm, where the pi and qj are prime, then n = m and, after
renumbering, pi = ±qi for all i.
[We allow negative primes, so that, for example, -17 is prime. This is consistent with the
general definition of prime element in an integral domain; see Section .]
The Integers Modulo m If a and b are integers and m is a positive integer ≥ 2,
we write a ≡ b mod m, and say that a is congruent to b modulo m,ifa − b is divisible by
m. Congruence modulo m is an equivalence relation, and the resulting equivalence classes
are called residue classes mod