90 6. Integers, Divisors, and Primes
0 200 400 600 800 1000
FIGURE 6.1. A bar chart of primes up to 1000.tation, thatit is unique. What this means is that there is no other way of
writingnas a product of primes (except, of course, we can multiply the
same primes in a different order). To prove this takes some sophistication
(as we’ll see in the next section), and to recognize the necessity of such a
result was quite an accomplishment; but this is all more than 2000 years
old!
It is really surprising that, even today, no efficient way is known tofind
such a decomposition. Of course, powerful supercomputers and massively
parallel systems can be used to find decompositions by brute force for fairly
large numbers; the current record is around 140 digits, and the difficulty
grows very fast (exponentially) with the number of digits. To find the prime
decomposition of a given number with 400 digits, by any of the known
methods, is way beyond the possibilities of computers in the foreseeable
future.
6.3 Factorization into Primes
We have seen that every integer larger than 1 that is not a prime itself
can be written as a product of primes. We can even say thateverypositive
integer can be written as a product of primes: Primes can be considered as
“products with one factor,” and if you wish, the integer 1 can be thought
of as the “empty product.” With this in mind, we can state and prove the
following theorem, announced above, sometimes called the “Fundamental
Theorem of Arithmetic”.
Theorem 6.3.1Every positive integer can be written as the product of
primes, and this factorization is unique up to the order of the prime factors.
Proof. We prove this theorem by a version of induction, which is some-
times called the “minimal criminal” argument. The proof is indirect: we
suppose that the assertion is false, and using this assumption, we derive a
logical contradiction.