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!
- Log in to post comments
Ah, the failure of unique factorization for a general complex-valued ring... Wasn't this originally discovered through the failure of a proof for Fermat's Last Theorem?
Kummer tried to prove Fermat's Last Theorem by working with an extension of the integers within which he could factor the Fermat equation. Specifically, if we consider the case of FLT with exponent p, he adjoined a p-th root of unity to the integers, in much the same way as I adjoined the square root of -5 to the integers above. His proof was correct so long as his extended ring was a unique factorization domain. Sadly, that is not true in general. On the other hand, it is true for primes smaller than 23, so Kummer's efforts were not completely wasted.
I don't if that was the actual discovery of non-unique factorization, but it certainly gave new relevance to the idea.
What's purple and commutes?
An abelian grape!
Also: Dammit, doesn't render properly in Opera! Off to play with settings, I suppose...
One neat thing about the Fundamental Theorem of Arithmetic is that is follows rather quickly that all non-square integers have irrational square roots.
Let a be a nonsquare integer, and let's assume that m/n is a square root of a. Then m^2 = an^2. By the Fundamental Theorem, m, n, and a are factorable into powers of primes. The powers of primes in m^2 must be even (since it can be factored into m*m, so every prime divisor of m is twice a prime divisor of m^2), and similarly the powers of primes in n^2 must be even. Not all powers of primes in a can be even, for if they were, then a would be square. Therefore, there must exist a prime p that divides a with an odd power b. Therefor, p must divide an^2 with an odd power. By assumption m^2 = an^2, and the uniqueness of the Fundamental Theorem implies that p divides m^2 and an^2 to the same power. But p is an even powered divisor of m^2 and an odd powered divisor of an^2, which is a contradiction. Therefore, a cannot have a rational square root m/n.
Huh. So it doesn't.
The script was changed to render the images as SVG rather than PNG, but it looks like Opera has no problem with SVG in and of itself.
Indeed, I just copied and pasted the call to appspot.com for one of the equations (that is, this string:
http://mathcache.appspot.com/?tex=%5Clarge%20%5Cparstyle%20%5Cpng%20%5C…
)
into my Opera address bar, and it does render OK in Opera. So it looks like the problem is with the underlying Javascript.
I was having problems before with some characters being rendered ridiculously large (in Firefox), but that is no longer as bad as it was (although some lines are still larger than others). Browser bug or server bug?
Chromium actually works the best of all -- characters are rendered darker and heavier than in Firefox, and they are all of them a reasonable size.
0.14076043434902338822275...
Geoffrey Landis and Jonathan Vos Post (personal communication) show that this constant equals ((P2)^2 + P4)/2, where P2 and P4 are constants in A085548 and A085964, respectively.
http://www.research.att.com/~njas/sequences/A117543
A117543 Decimal expansion of the sum of the reciprocals of squared semiprimes.
Semiprimes (or biprimes) being products of two primes, i.e. numbers of the form p*q where p and q are primes, not necessarily distinct. {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 121, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 169, 177, 178, 183, 185, 187, ...}
The graph of this sequence of semiprimes appears to be a straight line with slope 4. However, the asymptotic formula shows that the linearity is an illusion and in fact
a(n)/n ~ log n / log log n goes to infinity. See also the graph of A066265 = number of semiprimes < 10^n.
Followup: Looks like Firefox has some sort of browser bug. I cleared my cache and refreshed, and the page once again has some characters ridiculously large.
Some, but not all, instances of x, p1, and b, look like they are 72 pts or so.
Feh.
... and immediately after posting that last, everything is the right size, and the same size. Including the stuff that was large but not as large as 72 pts before.
Damn intermittent bugs.
Owlmirror -
Yes, the inline math does not format quite right. That's why as much as possible I tried to stick with display math.
I'm afraid I have never heard of Opera, at least not in this context. Is it another browser?
Yup!
Last of the Big 5 (IE, FF, Chrome, Safari, Opera)
http://en.wikipedia.org/wiki/Browser_usage_share
If anybody ever wants one or two hundred tabs open at the same time, then Opera is the way to go, hands down. Just sayin!
Thanks all for putting up with the joys of accidental beta testing. :)
Math displays on Opera now. On Opera, my code was creating image tags with an SVG src=, which Safari and Chrome allow (and actually need for scaling to work right). Instead, it needed to make object tags like it does for Firefox, and now it does.
The Firefox size problem is a fun one -- I didn't run into it in my testing, but Firefox sometimes gets SVG sizes wrong according to http://e.metaclarity.org/52/cross-browser-svg-issues/ , so I'll just have to include explicit width and height in the markup. The relevant bit is:
"Firefox does fine with the -version most of the time and obtains its size correctly (most of the time). Scaling works fine (CTRL+Mousewheel) in that case. I say âmost of the timeâ because sometimes, correct object dimensions are only applies after reloading the page (when this bug happens, some SVGs will be vastly bigger than they should be, and others a lot smaller)." (emphasis mine)
I also noticed the problem with vertical alignment of inline math -- I don't know if I can get that perfect but I can definitely make it better than it is now.
Randall --
Once again, thanks for the help.
Tweaked the script some more. Works for me in the latest versions of everything and vertical alignment is closer to right. Made lots of changes, so if it doesn't work for somebody, let me know what browser and version.
Hi. I have created an intuitive explanation of the proof above here:
http://math4allages.wordpress.com/2010/06/21/prime-series-2/
You may want to check it out.