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 a|b, 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
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 = x0m + y0n. 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 =
and so, solving for r,
However, this is a contradiction because p was the smallest element of S. Thus p|m. Similarly
Now suppose q divides both m and n. Then m = qx and n = qy for integers, x and y.
showing q|p. Therefore, p =
There is a relatively simple algorithm for finding
which will be discussed
now. Suppose 0
< m < n
are integers. Also suppose the greatest common
. Then by the Euclidean algorithm, there exist integers q,r
Now d divides n and m so there are numbers k,l such that dk = m,dl = n. From the above
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
Procedure 1.10.4 To find the greatest common divisor of m,n where 0 < m < n, replace
+ r for r < m. This new pair of numbers has
the same greatest common divisor. Do the process to this pair and continue doing this till
you obtain a pair of numbers where one is a multiple of the other. Then the smaller is the
sought for greatest common divisor.
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
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.
Theorem 1.10.7 If p is a prime and p|ab then either p|a or p|b.
Proof: Suppose p does not divide a. Then since p is prime, the only factors of p are 1 and p so
= 1 and therefore, there exists integers,
Multiplying this equation by b yields
Since p|ab, ab = pz for some integer z. Therefore,
and this shows p divides b. ■
Theorem 1.10.8 (Fundamental theorem of arithmetic) Let a ∈ ℕ∖
. Then a
i=1npi where pi are all prime numbers. Furthermore, this prime factorization is unique
except for the order of the factors.
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
where the pi and qj are all prime, there is no way to reorder the qk such that m = n and pi = qi
for all i, and n + m is the smallest positive integer such that this happens. Then by
Theorem 1.10.7, p1|qj for some j. Since these are prime numbers this requires p1 = qj.
Reordering if necessary it can be assumed that qj = q1. Then dividing both sides by
p1 = q1,
Since n + m was as small as possible for the theorem to fail, it follows that n− 1 = m− 1 and the
prime numbers, q2,
can be reordered in such a way that pk
for all k
for all i
because it was already argued that p1
and this results in a contradiction.
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 anλn + an−1λn−1 +
+ a0, an≠
0 where the ai come from a field of scalars. Two polynomials are equal means
that the coefficients match for each power of λ. The degree of a polynomial is the
largest power of λ. Thus the degree of the above polynomial is n. Addition of polynomials
is defined in the usual way as is multiplication of two polynomials. The leading term in the
above polynomial is anλn. The coefficient of the leading term is called the leading coefficient.
It is called a monic polynomial if an
Lemma 1.10.10 Let f
0 be polynomials. Then there exist polynomials, q
where the degree of r
is less than the degree of g
. These polynomials q
Proof: Suppose that f
is never equal to 0 for any
. If it is, then the
conclusion follows. Now suppose
and the degree of r
m ≥ n
is the degree of g
. Say the leading term of
while the leading term of g
. Then letting a
has the same leading
. Thus the degree of
is no more than
Denote by S the set of polynomials f
Out of all these polynomials, there exists
one which has smallest degree r
. Let this take place when
. Then by the above
argument, the degree of
is less than the degree of
. Otherwise, there is one which has
smaller degree. Thus
As to uniqueness, if you have r
which work, then you would
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
and so, matching coefficients implies that