First recall Theorem 1.9.10, the Euclidean algorithm.
Theorem 1.10.1 Suppose 0 < a and let b ≥ 0. Then there exists a unique integer p and real number r such that 0 ≤ r < a and b = pa + r.
The following definition describes what is meant by a prime number and also what is meant by the word “divides”.
Definition 1.10.2 The number, a divides the number, b if in Theorem 1.9.10, r = 0. That is there is zero remainder. The notation for this is ab, read a divides b and a is called a factor of b. A prime number is one which has the property that the only numbers which divide it are itself and 1. The greatest common divisor of two positive integers, m,n is that number, p which has the property that p divides both m and n and also if q divides both m and n, then q divides p. Two integers are relatively prime if their greatest common divisor is one. The greatest common divisor of m and n is denoted as
There is a phenomenal and amazing theorem which relates the greatest common divisor to the smallest number in a certain set. Suppose m,n are two positive integers. Then if x,y are integers, so is xm + yn. Consider all integers which are of this form. Some are positive such as 1m + 1n and some are not. The set S in the following theorem consists of exactly those integers of this form which are positive. Then the greatest common divisor of m and n will be the smallest number in S. This is what the following theorem says.
Theorem 1.10.3 Let m,n be two positive integers and define

Then the smallest number in S is the greatest common divisor, denoted by
Proof: First note that both m and n are in S so it is a nonempty set of positive integers. By well ordering, there is a smallest element of S, called p = x_{0}m + y_{0}n. Either p divides m or it does not. If p does not divide m, then by Theorem 1.9.10,

where 0 < r < p. Thus m =

However, this is a contradiction because p was the smallest element of S. Thus pm. Similarly pn.
Now suppose q divides both m and n. Then m = qx and n = qy for integers, x and y. Therefore,

showing qp. Therefore, p =
There is a relatively simple algorithm for finding
 (1.1) 
Now d divides n and m so there are numbers k,l such that dk = m,dl = n. From the above equation,

Thus d divides both m and r. If k divides both m and r, then from the equation of 1.1 it follows k also divides n. Therefore, k divides d by the definition of the greatest common divisor. Thus d is the greatest common divisor of m and r but m + r < m + n. This yields another pair of positive integers for which d is still the greatest common divisor but the sum of these integers is strictly smaller than the sum of the first two. Now you can do the same thing to these integers. Eventually the process must end because the sum gets strictly smaller each time it is done. It ends when there are not two positive integers produced. That is, one is a multiple of the other. At this point, the greatest common divisor is the smaller of the two numbers.
Procedure 1.10.4 To find the greatest common divisor of m,n where 0 < m < n, replace the pair
Example 1.10.5 Find the greatest common divisor of 165 and 385.
Use the Euclidean algorithm to write

Thus the next two numbers are 55 and 165. Then

and so the greatest common divisor of the first two numbers is 55.
Example 1.10.6 Find the greatest common divisor of 1237 and 4322.
Use the Euclidean algorithm

Now the two new numbers are 1237,611. Then

The two new numbers are 15,611. Then

The two new numbers are 15,11. Then

The two new numbers are 11,4

The two new numbers are 4,3. Then

The two new numbers are 3,1. Then

and so 1 is the greatest common divisor. Of course you could see this right away when the two new numbers were 15 and 11. Recall the process delivers numbers which have the same greatest common divisor.
This amazing theorem will now be used to prove a fundamental property of prime numbers which leads to the fundamental theorem of arithmetic, the major theorem which says every integer can be factored as a product of primes.
Proof: Suppose p does not divide a. Then since p is prime, the only factors of p are 1 and p so follows

Multiplying this equation by b yields

Since pab, ab = pz for some integer z. Therefore,

and this shows p divides b. ■
Theorem 1.10.8 (Fundamental theorem of arithmetic) Let a ∈ ℕ∖
Proof: If a equals a prime number, the prime factorization clearly exists. In particular the prime factorization exists for the prime number 2. Assume this theorem is true for all a ≤ n− 1. If n is a prime, then it has a prime factorization. On the other hand, if n is not a prime, then there exist two integers k and m such that n = km where each of k and m are less than n. Therefore, each of these is no larger than n − 1 and consequently, each has a prime factorization. Thus so does n. It remains to argue the prime factorization is unique except for order of the factors.
Suppose

where the p_{i} and q_{j} are all prime, there is no way to reorder the q_{k} such that m = n and p_{i} = q_{i} for all i, and n + m is the smallest positive integer such that this happens. Then by Theorem 1.10.7, p_{1}q_{j} for some j. Since these are prime numbers this requires p_{1} = q_{j}. Reordering if necessary it can be assumed that q_{j} = q_{1}. Then dividing both sides by p_{1} = q_{1},

Since n + m was as small as possible for the theorem to fail, it follows that n− 1 = m− 1 and the prime numbers, q_{2},
There is a similar division result for polynomials. This will be discussed more intensively later. For now, here is a definition and the division theorem.
Definition 1.10.9 A polynomial is an expression of the form a_{n}λ^{n} + a_{n−1}λ^{n−1} +

where the degree of r
Proof: Suppose that f

and the degree of r

Denote by S the set of polynomials f
As to uniqueness, if you have r

Now if the polynomial on the right is not zero, then neither is the one on the left. Hence this would involve two polynomials which are equal although their degrees are different. This is impossible. Hence r