Unknown

1.6. Basic Number Theory and Modular Arithmetic 31

an integer c for which b = UC. Thus, for example, 371111 since 111 = 37 x 3.
The only integers which divide every other integer are +l and -1. Every
integer divides 0, since, for each integer k, we can write 0 = k0.
If aJb, then Ial 2 lbl, so that, if ulb and blu, then either a = b or a = -b.
For two nonzero integers a and b, an integer d such that dlu and dlb is called
a common divisor of a and b. There is a unique largest integer g which is
a common divisor of a and b; this is the greatest common divisor of a and
b. We denote g by gcd(u, b).
If ulc, then c is a multiple of a. If c is a multiple of both a and b, then c is
a common multiple of a and b. There is a unique smallest positive integer
which is a multiple of both a and b; this is the least common multiple of a
and b.
The greatest common divisor of two integers is a multiple of every com-
mon divisor. The least common multiple divides every common multiple.
An integer p is prime if and only if p is positive, p # 1 and the only
positive divisors of p are 1 and p. A pair of integers is coprime if their
greatest common divisor is 1.
A fundamental result is the following.

Division Theorem. Let u, b belong to Z with a > 0. There are integers q
(quotient) and r (remainder) such that

b=qu+r and O<r<u.

Furthermore, q and r are uniquely detewnined. That is, if the foregoing
conditions are satisfied with (q, r) replaced by (q’,r’), then r’ = r and
q’ = q.

Exercises

1. The Euclidean algorithm. There is an ancient algorithm for finding the
   greatest common divisor of two given numbers which makes repeated
   use of the Division Theorem. The original context for the algorithm
   was not whole numbers but what the Greek geometers called magni-
   tudes. Length is an example. One magnitude measures a second if the
   second is an positive integer multiple of the first; two magnitudes are
   commensurable if there is a magnitude which measures them both.
   In Book X, Propositions 1, 2, and 3, of his Elements, Euclid presents
   a practical method for determining whether or not two magnitudes
   are commensurable, and, in the latter case, of arriving at the greatest
   common measure. The Greeks might have used these results in ge-
   ometry, for example, to show that the side and diagonal of a square
   are incommensurable.
   To see how Euclid’s algorithm works in a numerical situation, let us
   find the greatest common divisor of 418 and 1606. Divide the smaller