Posted by In my last math post I casually mentioned that the sum of the reciprocals of the primes diverges. That is
\[
\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13}+ \dots=\infty
\]
That seems like a hard thing to prove. Certainly none of the traditional convergence tests from Calculus II will get the job done. The problem is how to “get at” the primes. Plainly we need to do something clever.
As it happens, the proof is a bit tricky. It has a lot of ingredients, too. On the other hand, each one of those ingredients is pretty interesting in its own right. So how about a series of posts building up to the proof of the equation above?
First ingredient: The Fundamental Theorem of Arithmetic!
The fundamental theorem of arithmetic says that every positive integer greater than one can be written as a product of prime numbers in exactly one way. (We should add the caveat that two factorizations differing only by the order in which we write the factors are considered to be identical). Of course, if the integer is itself prime then we consider it to be trivially the product of primes. That way we do not have to add annoying extra clauses to the statement of the theorem to account for the primes themselves.
The theorem thus has two parts: Existence and Uniqueness. The first part is easy, the second part only slightly more challenging.
Let’s do existence. If the theorem is false then there is a smallest integer $x$ that cannot be written as the product of prime numbers. It follows that $x$ is not prime, and is therefore composite. That means we can factor it into the product of two smaller integers, say
\[
x = r \cdot s
\]
But since $r$ and $s$ are smaller than $x$, we know they can be factored into primes. But that would imply that $x$ can be so factored as well, and we have reached a contradiction. So every positive integer greater than one can be expressed as the product of prime numbers.
What about uniqueness? Well, that requires a little fact: If a prime number divides the product of two other numbers, then one of those two other numbers is a multiple of the prime. To make things more concrete, if, say, seven divides the product of two numbers, then one of the two numbers is already a multiple of seven.
That particular statement is just tricky enough to prove that I would rather not bother. Click here if you want to see how the trick is done. But I think things become very clear just by considering what goes wrong when you are not dealing with a prime number.
Note, for example, that
$$6 \ | \ (8 \times 9),$$
where that vertical line means “divides.” In other words, seventy-two is a multiple of six. But neither eight nor nine is a multiple of six on its own!
This is possible because the number six is made by multiplying together a two and a three. The eight brings the two to the party while the nine brings the three. The ingredients for making six can be spread across the two factors, and that is why neither one of them had to be a multiple of six by itself. That is precisely what you cannot do with a prime. There are no “ingredients” for making a prime number. It just is what it is.
Now we can establish uniqueness. Suppose we had two different prime factorizations for the same number. Then we would have an equation like this:
\[
p_1^{a_1}p_2^{a_2} \dots p_k^{a_k} =
q_1^{b_1}q_2^{b_2} \dots q_\ell^{b_\ell}
\]
where the $p$’s and $q$’s are primes. But now we see that $p_1$ divides the left-hand side. That means it must divide the right-hand side as well. But that implies one of the factors on the right must be a multiple of $p_1$. Since all the $q$’s are themselves prime, we see that $p_1$ must actually be equal to one of the $q$’s.
Now we can divide $p_1$ from both sides and repeat the process anew. In this way we will cancel out all the primes and find that the two factorizations could only have differed by the ordering of the factors. Nice!
Let’s kick it up a notch. Suppose we consider a set a bit more complicated that the integers. For example, we could define the set
\[
\mathbb{Z}(\sqrt{-5})=\left\{a+b\sqrt{-5} \mid a, b \in \mathbb{Z} \right\}
\]
The fancy Z is the universally accepted symbol for the integers. The set on the right asks us to consider all the symbols of the form
$$a+b\sqrt{-5}$$
where $a$ and $b$ are integers. The more familiar integers are elements of this set. Just let $b$ equal zero.
We can add and multiply within this set by following the normal algebraic rules for such things. This implies that our new set, just like the integers, is a “ring”, meaning simply that it is an environment in which you can add and multiply in a way that satisfies the normal axioms for those operations.
(Technically we should say these sets are “commutative rings” which means that multiplication is commutative. We also have properties like associativity, and a distributive property that relates addition to multiplication. Those are the sorts of things I mean when I talk about the normal axioms.)
So we can ask the question, does unique factorization still hold when we enlarge the integers in this way? The answer is no! Consider:
\[
6 = 2 \times 3 = \left(1+\sqrt{-5}\right)\left(1-\sqrt{-5}\right)
\]
I have obscured a fair number of technical details here. It can be shown that those factors on the right are “irreducible” meaning roughly that they cannot be expressed as the product of two other elements of the ring in a nontrivial way. In rings more general than the integers there is an important distinction between “irreducible” and “prime”. Perhaps we will explore these differences in a future post.
The bottom line is that all of the normal questions you might ask of the integers concerning primes, factorization and divisibility can also be asked in any commutative ring. In these more general environments you cannot take prime factorization for granted. But once you start investigating these sorts of questions you enter the realm of algebraic number theory, and that is definitely a different post!
July 26, 2010
July 26, 2010
July 26, 2010
July 26, 2010
July 27, 2010
July 27, 2010
July 27, 2010
July 29, 2010
August 20, 2010