as θvaries from zero to 360°, again for Rlarge, p(z)
closely traces a circle of large radius Rn(again winding
around ntimes). If Ris sufficiently large, this circle is
sure to enclose the point (0,0) in the complex plane. If
Rshrinks to the value zero, then the trace of p(z) as θ
varies is a circle of radius 0 about the point p(0) = a0.
That is, the trace of p(z) is the point a0in the complex
plane. Between these two extremes, there must be some
intermediate value of Rfor which the trace of p(z)
passes through the origin (0,0). That is, there is αvalue
on the circle of this radius Rfor which p(α) = 0. This
proves the theorem.
fundamental theorem of arithmetic (unique factor-
ization theorem) This fundamental result from arith-
metic asserts:
Every integer greater than one can be
expressed as a product of prime factors in one
and only one way, up to the order of the fac-
tors. (If the number is already prime, then it is
a product with one term in it.)
For example, the number 100 can be written as 2 ×2 ×
5 ×5. The fundamental theorem of arithmetic asserts
that the number 100 cannot be written as a product of
a different set of primes.
Many elementary school children are familiar
with the process of factoring with the aid of a factor
tree. It is often taken as self-evident that the prime
numbers one obtains as factors will always be the
same, no matter the choices one makes along the way
to construct the tree. However, a proof of this is
required.
It is straightforward to see that any number nhas,
at the very least, some prime factorization: If nis
prime, then nis a product of primes with one term in
it. If nis not prime, the ncan be written as a product
of two factors: n= a×b. If both aand bare prime,
there is nothing more to do. Otherwise, aand bcan
themselves be factored. Continue this way. This process
stops when all factors considered are prime numbers.
That the prime factorization is unique follows from
the following property of prime numbers:
If a product a×bequals a multiple of a prime
number p, then one of aor bmust itself be a
multiple of p.
(To see why this is true, suppose that ais not already a
multiple of p. Since pis prime, this means that the only
factor pand acan have in common is 1. By the
E
UCLIDEAN ALGORITHM
we can thus find numbers x
and yso that 1 = px + by. Multiplying through by b
gives: b= pbx + aby. The first term in this sum is a
multiple of p, and so is the second since ab is. This
shows that bmust be a multiple of p, if ais not.)
Suppose, for example, we found the following two
prime factorizations of the same number:
7 ×13 ×13 ×29 ×29 ×29 ×41 = 19 ×19 ×23
×23 ×37 ×61
The quantity on the left is certainly a multiple of 7,
which means the quantity on the right is too. By the
property described above, this means that one of the
factors: 19, 23, 37, or 61 is a multiple of seven. Since
each of these factors is prime, this is impossible. In gen-
eral, this line of reasoning shows that the primes
appearing in two factorizations of a number must be
the same. (It also shows, for example, that no power of
7 could ever equal a power of 13, and that no power of
6 is divisible by 14.)
E
UCLID
, of around 300
B
.
C
.
E
., was aware that the
prime factorizations of numbers are unique.
Note that, in these considerations, it is vital that 1
not be regarded as prime—otherwise every number
would have infinitely many different representations as
a product of prime factors. (For example, we could
write: 6 = 2 ×3 = 1 ×2 ×3 = 1 ×1 ×2 ×3, and so on.)
Writing numbers in terms of their prime factoriza-
tions helps one quickly identify common factors and
common multiples. For example, if a= p1n
1
p2n
2
…pkn
k
and b= p1m
1
p2m
2
…pkm
k
, with the numbers niand mi
possibly zero (this ensures that each number is
expressed via the same list of primes), then the
GREAT
-
EST COMMON DIVISOR
of aand bis the number:
gcd(a,b) = p1α
1
p2α
2
…pkα
k
with each αithe smaller of niand mi, and the
LEAST
COMMON MULTIPLE
of aand bis:
lcm(a,b) = p1β
1
p2β
2
…pkβ
k
with each βithe larger of niand mi. This proves the
relationship:
210 fundamental theorem of arithmetic