as θ varies from zero to 360°, again for R large, p(z)
closely traces a circle of large radius R
n (again winding
around n times). If R is sufficiently large, this circle is
sure to enclose the point (0,0) in the complex plane. If
R shrinks to the value zero, then the trace of p(z) as θ
varies is a circle of radius 0 about the point p(0) = a 0 .
That is, the trace of p(z) is the point a 0 in the complex
plane. Between these two extremes, there must be some
intermediate value of R for which the trace of p(z)
passes through the origin (0,0). That is, there is α value
on the circle of this radius R for which p(α) = 0. This
proves the theorem.
fundamental theorem of arithmetic (unique factorization theorem) This fundamental result from arithmetic 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 factors. (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 n has,
at the very least, some prime factorization: If n is
prime, then n is a product of primes with one term in
it. If n is not prime, the n can be written as a product
of two factors: n = a × b. If both a and b are prime,
there is nothing more to do. Otherwise, a and b can
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 × b equals a multiple of a prime
number p, then one of a or b must itself be a
multiple of p.
(To see why this is true, suppose that a is not already a
multiple of p. Since p is prime, this means that the only
factor p and a can have in common is 1. By the
EUCLIDEAN ALGORITHM we can thus find numbers x
and y so 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 b must be a multiple of p, if a is 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 general, 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.)
EUCLID, 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 factorizations helps one quickly identify common factors and
common multiples. For example, if a = p 1
n 1 p 2
n 2 …p k
n k
and b = p 1
m 1 p 2
m 2 …p k
m k , with the numbers n i and m i
possibly zero (this ensures that each number is
expressed via the same list of primes), then the GREATEST COMMON DIVISOR of a and b is the number:
gcd(a,b) = p 1
α 1 p 2
α 2 …p k
α k
with each α i the smaller of n i and m i , and the LEAST
COMMON MULTIPLE of a and b is:
lcm(a,b) = p 1
β 1 p 2
β 2 …p k
β k
with each β i the larger of n i and m i . This proves the
relationship:
210 fundamental theorem of arithmetic
closely traces a circle of large radius R
n (again winding
around n times). If R is sufficiently large, this circle is
sure to enclose the point (0,0) in the complex plane. If
R shrinks to the value zero, then the trace of p(z) as θ
varies is a circle of radius 0 about the point p(0) = a 0 .
That is, the trace of p(z) is the point a 0 in the complex
plane. Between these two extremes, there must be some
intermediate value of R for which the trace of p(z)
passes through the origin (0,0). That is, there is α value
on the circle of this radius R for which p(α) = 0. This
proves the theorem.
fundamental theorem of arithmetic (unique factorization theorem) This fundamental result from arithmetic 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 factors. (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 n has,
at the very least, some prime factorization: If n is
prime, then n is a product of primes with one term in
it. If n is not prime, the n can be written as a product
of two factors: n = a × b. If both a and b are prime,
there is nothing more to do. Otherwise, a and b can
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 × b equals a multiple of a prime
number p, then one of a or b must itself be a
multiple of p.
(To see why this is true, suppose that a is not already a
multiple of p. Since p is prime, this means that the only
factor p and a can have in common is 1. By the
EUCLIDEAN ALGORITHM we can thus find numbers x
and y so 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 b must be a multiple of p, if a is 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 general, 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.)
EUCLID, 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 factorizations helps one quickly identify common factors and
common multiples. For example, if a = p 1
n 1 p 2
n 2 …p k
n k
and b = p 1
m 1 p 2
m 2 …p k
m k , with the numbers n i and m i
possibly zero (this ensures that each number is
expressed via the same list of primes), then the GREATEST COMMON DIVISOR of a and b is the number:
gcd(a,b) = p 1
α 1 p 2
α 2 …p k
α k
with each α i the smaller of n i and m i , and the LEAST
COMMON MULTIPLE of a and b is:
lcm(a,b) = p 1
β 1 p 2
β 2 …p k
β k
with each β i the larger of n i and m i . This proves the
relationship:
210 fundamental theorem of arithmetic