Another Look at Prime Numbers

Primes are numeric celebrities: they're used in movies, security codes, puzzles, and are even the subject of forlorn looks from university professors.

But mathematicians delight in finding the first 20 billion primes, rather than giving simple examples of why primes are useful and how they relate to what we know. Somebody else can discover the "largest prime" -- today let's share intuitive insights about why primes rock:

• Primes are building blocks of all numbers. And just like in chemistry, knowing the chemical structure of a material helps understand and predict its properties.

• Primes have special properties like being difficult to determine (yes, even being difficult can be a positive trait). These properties have applications in cryptography, cycles, and seeing how other numbers multiply together.

So what are prime numbers again?

A basic tenet of math is that any number can be written as the multiplication of primes. For example:

• 9 = 3 * 3 = 3²
• 12 = 2 * 2 * 3 = 2² 3
• 100 = 4 * 25 = 2 * 2 * 5 * 5 = 2² 5²

And primes are numbers that can't be divided further, like 3, 5, 7, or 23. Even the number 2 is prime, if you think about it. And the number 1?

Well, 1 is special and isn't considered prime, since things get crazy because 1 = 1 * 1 * 1... and so on. Even mathematicians take shortcuts sometimes, and leave 1 out of the discussion.

Rewriting a number into primes is called prime decomposition, math speak for "find the factors". Primes seem simple, right?

Well, not really. It turns out that

• Primes are infinite and we'll never run out (see proof).
• Primes appear randomly distributed
• Primes show up in strange places, like quantum mechanics
• Prime decomposition is hard. So far, trial-and-error is the best way to break a number into primes. And that's slow.

God, nature, or the flying spaghetti monster -- whatever determined the primes, it made a whole lot of 'em and distributed them in a quirky way.

Analogy: Prime Numbers and Chemical Formulas

Prime numbers are like atoms. We can rewrite any number into its "chemical formula" that shows its parts. In chemistry, we can say a water molecule is really H₂0:

• Water = H₂0 = two hydrogens and one oxygen

And for a number, we can break it into primes

• 12 = 2 * 2 * 3 = 2² 3 = two "2s" and one "3"

Neat relationship, right? In chemistry the "exponent" happens to go underneath -- I'd really prefer exponents above, but the American Chemical Society hasn't replied to my letters.

Why is this interesting? Well, when chemists arranged their basic elements into the periodic table, new insights emerged:

• New elements were "predicted" by the gaps in the table
• Elements in the same row or column shared certain properties
• Trends (like increasing reactivity) emerged as you moved around the table

Not bad for reorganizing existing data, eh? Similarly, we can imagine putting the primes (numerical "elements") into a table. But there's a problem.

Nobody knows what the table looks like! Primes are infinite and appear at random. We've tried for centuries to find a pattern, but we can't. We have no idea where the gaps are or when the next prime is coming. (That's not quite true -- there's interesting hypotheses and conjectures, but the riddle is not solved).

But we won't cry about it, breaking our pencil and sobbing home. You and I are going to make use of the primes even though we don't know every detail.

Organic Chemistry and Functional Groups

I'm no chemistry expert, but I can see a relationship to the primes. Chemical elements have properties based on their location in the periodic table of the elements:

• Atoms in group 18 (Neon, Argon) are the noble gases. They don't react and won't blow up in your face.
• Atoms in group 14 (Carbon, Silicon) bond well. They're great building blocks for other elements.
• Atoms in group 1 (Sodium, Potassium, etc.) are very reactive. Drop 'em in water and see them explode.

And in organic chemistry there's an idea of a functional group: several atoms can determine the class of the entire molecule. For example:

• Alcohols are a certain carbon-hydrogen chain with an OH group at the end.
• Methanol, ethanol, and other alcohols share similar properties because of this OH functional group.

Those are the basics, if I didn't mess it up. Now let's see what happens when we treat primes like chemicals.

First Example: Guessing "Evenness"

In general, an "organic" chemical contains carbon (not quite, but it's a good starting point). No matter what elements you mix together, if you never add any carbon then you can't create an organic compound.

"Evenness" works the same way. A number is even if it has a 2 in its prime decomposition -- i.e., 2 was used to "make" the number. There could be a single 2 or fifty; if you have a single 2, you are even, and that's that. If you don't have a 2, you're odd.

Now, remember those math questions that ask how odd and even numbers multiply?

• Even times odd is ... (even or odd?)
• Even times even is ... (even or odd?)
• Odd times odd is ... (even or odd?)

How would you solve this? Guess? Try a few examples? ("Let's see, 3 times 2 is.. 6, but 3 times 3 is 9... so...").

Here's one way to think about it. Multiplication is combining the "prime formulas" for the numbers. Since even numbers contain a "2" somewhere, we can guess that:

• Even times odd is even. We started with a 2. It doesn't matter what else we put in.
• Even times even is even. We started with a 2 and put in another for good measure.
• Odd times odd is odd. We never put in a 2 the whole time, so we stay odd.

Pretty cool, eh? And since 2 is prime, we know we can't "manufacture" a 2 by combining other numbers together.

Thank you prime chemistry, for giving us another way to think about this problem. Now you can even answer questions like this:

• What's odd * odd * odd * odd * even?

It's even, since we mixed in a 2 at the end.

Another Example: Ending with 0

I've read your mind: you want another chemical example, this time with functional groups.

Suppose a number has a "2*5" functional group -- it has one or more 2s and one or more 5s. For example:

• 10 = 2 * 5
• 40 = 2 * 2 * 2 * 5
• 90 = 3 * 3 * 2 * 5

Notice a pattern? If a number has a 2 * 5 "functional group", it ends in 0.

Why? Well, 2 * 5 = 10. So having 2 * 2 * 2 * 5 is really like having (2 * 2) * 10. Any whole number multiplied by 10 ends in 0. In general,

• (some other primes) * (2 * 5) = a number ending in 0

So just by looking at the "prime formula" you can determine that the number ends with a 0. You never had to do the multiplication out.

And Another Example: Sum of Digits

What's that? You want another example with functional groups? If you insist.

Let's think about numbers with the "3*3" functional group. A number could have 400 threes, but as long as there's at least 2 we're interested. If a number has (3*3) it means

• It is divisible by 9
• The sum of the digits is divisible by 9 (we can prove this later -- take my word for now).

Here's an example:

• 18 = 2 * 3 * 3. It has the (3*3) functional group. The sum of the digits is 1 + 8 = 9, which is divisible by 9.
• Take a strange number like 31 * 3 * 3 = 279. It has a (3*3) functional group, and the sum of digits is 2 + 7 + 9 = 18. 18 is divisible by 9, so the property holds.

Again, this is pretty cool. We know something about the sum of digits just by finding a certain functional group in the prime decomposition of the number.

Primes in the Real World

Primes have properties that come in useful.

1. Large numbers are hard to factor. We essentially resort to trial-and-error when doing prime decomposition: one method is to keep trying to divide it by other numbers, up to its square root. The fact that primes and prime decompositions are "secret" can be a good thing for cryptography -- we'll get into this later.

2. Primes don't play well with other numbers. Prime numbers don't "overlap" with the regular numbers: they intersect at the last possible moment. For example, 4 and 6 "overlap" at 12, which is pretty early. Their first "required" overlap is at 4 * 6 = 24.

Primes, however, intersect at the last possible moment. 5 and 7, for example, only coincide at 35 (5*7). There's no intermediate value where they both show up.

You'd think a lack of rhythm would be a bad thing, but in nature it can be an advantage.

The cicada insect sprouts from the ground every 13 or 17 years. This means it has a smaller chance of "overlapping" with a predator's cycle, which could be at a more common 2 or 4-year cycle.

3. Primes are prime everywhere.

The movie "Contact" used primes as a universally understood sequence. It's a non-trivial sequence (2, 3, 5, 7, 11, 13) that would be hard to generate by accident (1, 0, 1, 0 could be made by a swinging pendulum, for example).

And prime numbers are prime in any number system. "1/3" is only a repeating fraction in base 10 (.33333), and you could even argue that pi (3.14159...) is not irrational in base "pi". But everyone can agree that certain numbers are prime and can't be divided. You can even transmit primes in a unary number system that lacks a decimal point:

II
III
IIIII
IIIIIII

etc. So primes are an infinite, non-repeating, universally-understood sequence, and a good choice for transmitting a message.

Conclusion

Don't hate the primes because they're different -- see how their properties can be useful. "Not fitting in" is a great if it means you don't overlap with a predator, right? Being hard to factor is great if you're making a secret message, right? For a long time primes were considered a purely theoretical curiosity, but lo and behold, we've found situations where they apply.

And that's a large part of math, in my opinion: seeing how strange properties can be useful or relate to the real-world. Math gives us rules, often for games we don't yet play. Our job is to find situations where we want to follow those rules.

There's much more I'd like to say in upcoming posts. If you want to dive into primes, check out Music of the primes which is a decent introduction to the issue of the primes, and motivated me to think about this topic.