**Abstract**

**1 Divisibility**

• Take questions and review some concepts from homework.

• Theorem ( Division algorithm ): If a, b ∈ Z and a ≠ 0, there exist unique
integers, q and

r, such that b = qa + r, where 0 ≤ r < |a|, or

Proof: Note that a = sgn(a)|a|, so we can consider the
case of a and b both positive.

The quotient is how many times a may be subtracted from b before b becomes
negative.

That is, q is largest integer n such that b - na is nonnegative; then r = b - qa.

– Let S = {b- na | n ∈ Z and b - na ≥ 0. Note that if b ≥ 0, then b - 0a = b ∈
S,

so S is not empty.

– Call r the smallest element of S. Note that r < |a|, since if r ≥ a, then 0 ≤

r - a = b - qa - a = b - (q + 1)a ∈ S, contrary to the assumption that r is the

smallest member of S.

– Uniqueness: Suppose that b = aq + r = aq' + r', where 0 ≤ r, r' < a. Then

r = b - aq and r' = b - aq' are both in S. Since elements of S differ by
multiples

of a, only one member lies in [0, a). Because r and r' both fall in this
interval, we

have r = r'. Then b - aq = b - aq', whence q = q'.

• Let be the set of divisors of n , and let
be the set of positive divisors of n.

• Definition: A natural number p > 1 is prime if the only
positive divisors of p are 1 and

p; that is, if = {1, p}. Note that 1 is
not prime.

• The set of prime numbers is often denoted by P.

• The set of natural numbers n > 1 that are not prime are called composite.

• The set of composite numbers is often denoted by C. Then N = {1} ∪ P ∪ C.

• Any composite number n can be written as a product of other numbers
, each

of which may be prime or composite. Recurse until you have a product of primes,

so: Theorem: Any natural number > 1 can be factored as a product of primes, n =

• Theorem: There are infinitely many prime numbers. Proof (Euclid): Suppose, to
the

contrary, that there is a largest prime number, so there are only a finite set
of them,

{. The number
is then not divisible by any of them, etc.

Note that this does not mean that 2 · 3 · 5 · 7 · 11· 13 + 1 = 30031 = 59 · 509
is prime!

(Also note that the prime factors of 30031 are both greater than 13.)

• Example: =
{±1,±2,±3,±6,±7,±9,±14,±18,±21,±42,±63,±126}

• Example: =
{±1,±2,±3,±5,±6,±10,±15,±25,±30,±50,±75,±150}

• Note that ∩
= {±1,±2,±3,±6} is the set of numbers that
simultaneously

divide 126 and 150. The set has a greatest element , namely 6, called the
greatest

common divisor of 126 and 150.

• Definition: Given integers m and n, not both zero , the greatest common divisor
(GCD)

of m and n, denoted by gcd(m, n), is the natural number d such that

– d|m and d|n, and

– u|m and u|n => d ≥ u.

• Example: To compute gcd(m, 0), note that =
Z\{0}, so ∩
= . The

greatest element of is |m|, so gcd(0,m) =
|m|.

• Definition: Two integers m and n, not both zero, are relatively prime if gcd(m,
n) = 1.

That is, m and n are relatively prime if they have no common factors other than
±1.

Note that two numbers do not need to be prime in order to be relatively prime;
for

example, 14 and 15 are relatively prime, even though neither is prime.

• Note that the definition of gcd and of relatively prime can be extended to
more than

two numbers. For example, gcd(30, 42, 66) is the maximum number in the set

, which is 6. Moreover, the numbers 30, 42
and 66 are not relatively prime,

but the numbers 30, 42 and 65 are relatively prime because
.

• The least common multiple (LCM) of m and n, not both
zero, is the smallest positive

integer that is a multiple of both m and n. It is denoted by lcm (m, n). We know
that

mn is a multiple of both m and n, so lcm (m, n) ≤ mn, which shows that lcm(m, n)

always exists.