Fundamental Theorem of Arithmetic
Let us begin by noticing that, in a certain sense, there are two kinds of natural number: composite numbers and prime numbers. Composite numbers we get by multiplying together other numbers. For example, \(6=2\times 3\). We say that 6 factors as 2 times 3, and that 2 and 3 are divisors of 6. Since \(1\times 6=6\) we call 1 and 6 divisors of 6 also; indeed 1 is a divisor of every number and every number is a divisor of itself.
The numbers other than itself that divide a given number are called its proper divisors, so the proper divisors of 6 are 1, 2, and 3. If a number has no proper divisors except 1, that number is called prime. (Only one positive integer has no proper divisors—1 itself. For this reason, 1 is considered neither composite nor prime.)
How many prime numbers are there? Well, lots:
\[\begin{eqnarray*} \mbox{Primes } & = & \{2,3,5,7,11,13,17,23,29,31,37,41, \\ & & \,\,43,47,53,59,61,67,71,73,79,83,89, \\ & & \,\,97,101,103,107,109,113,127,131, \\ & & \,\,137,139,149,151,157,163,167,173, \\ & & \,\,179,181,191,193,197,199,227,229, \\ & & \,\,233,239,241,251,257,263,269,271, \\ & & \,\,277,281,283,293,307,311,313, \ldots \} \end{eqnarray*} \]
Euclid proved that there isn’t a largest prime—in effect that the primes are infinite. In the 19th century the so-called Prime Number Theorem was proved, which describes the distribution of primes by giving a formula that closely approximates the number of primes less than a given integer.
The Fundamental Theorem of Arithmetic (FTA) tells us something important about the relationship between composite numbers and prime numbers. It is usually stated as follows:
Thm: Every natural number is either prime or can be factored as a product of primes in a unique way.
What does this mean? Let’s look at an example.
\[60=2\times 2\times 3\times 5\]
The FTA tells us that there is no way of factoring the number 60 into different primes than these – that this factorization is unique. (It’s true that we can factor 60 into, for example, 4 × 15, but then 4 and 15 aren’t prime, and if we factor them we’ll discover that we get right down to the same primes listed above.)
One way of interpreting the FTA is to say that the prime numbers are the building blocks, so to speak the bones, out of which the set of natural numbers is built. In the field of mathematics known as number theory (which Karl Gauss, the greatest mathematician since antiquity, called the “Queen of Mathematics”) this business of the structure of the natural numbers is a central concern. In this theory, many beautiful things about the natural numbers are proved.
As an exercise, it can be entertaining to write down all the natural numbers up to, say, 60 or so, and next to each one write down its prime factorization, or the word “prime” if it is prime. Doing this will greatly increase your appreciation of the underlying “structure” of the numbers we use every day.
We’ll get you started:
\[\begin{eqnarray*} 2 & = & prime \\ 3 & = & prime \\ 4 & = & 2 \times 2 \\ 5 & = & prime \\ 6 & = & 2 \times 3 \\ 7 & = & prime \\ 8 & = & 2 \times 2 \times 2 \\ 9 & = & 3 \times 3 \\ 10 & = & 2 \times 5 \\ 11 & = & prime \\ 12 & = & 2 \times 2 \times 3 \\ 13 & = & prime \\ & \vdots & \end{eqnarray*}\]
