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
^{2} - 12 = 2 * 2 * 3 = 2
^{2}3 - 100 = 4 * 25 = 2 * 2 * 5 * 5 = 2
^{2}5^{2}

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 don't have a pattern we can decipher****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 a "chemical formula" that shows its parts. In chemistry, we can say a water molecule is really H_{2}0:

- Water = H
_{2}0 = two hydrogens and one oxygen

And for a number, we can break it into primes

- 12 = 2 * 2 * 3 = 2
^{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 although we've tried for centuries to find a pattern, 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 8A**(Neon, Argon) are the noble gases. They don't react and won't blow up in your face.**Atoms in group 4A**(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 numbers 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
```

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.

## Leave a Reply

71 Comments on "Another Look at Prime Numbers"

Hi Kalid,

It was a good read. It would be interesting if you could explain the mechanism of cryptograhy intuitively using prime numbers !

Thank you,

Arun

The simple in the complex.

The complex in the simple.

Though I can’t explain why, I’ve been fascinated with prime numbers since I first learned about them as a child. On the one hand they seem so simple, yet their subtlety confounds great minds. They appear as the most basic of all building blocks, but they do so much.

I have, over the years, formed a theory; not about prime numbers, but about why they are so difficult to comprehend. Here’s my theory in terse verbiage (I don’t think Babelfish translates geek to English, so I’ll give you the English version after):

In viewing the body of number theory as a graphed network of axiomatic process, prime numbers (as they naturally are) inhabit a more fundamental tier than the mathematic community since antiquity would have us believe.

Here’s what I mean in plain words.

As you consider a bunch of different processes, and as you go from the more advanced down to the more fundamental, the ‘doing’ of it gets easier but the ‘explaining’ of it gets harder.

Here’s an Example for Free (exempli gratis if you didn’t know where e.g. came from)

Exponentiation.

I’ll give you two numbers, 2 and 3, then ask of you two tasks:

-first perform the calculation, 2^3 (easy, it’s eight)

-second, tell me why it is so

Takes a little more thought, but not too hard. It’s a shorthand for the more fundamental operation of multiplication. Take 2, write it out 3 times, multiply them all. To understand this, or to explain it, you have to understand exponents not at the level they are, but the level underneath them.

Multiplication.

Same two numbers.

-first can you do the work, 2*3=6 (easier than exponents)

-second, why is it so (harder than exponents)

It’s the same process, just a shorthand for the more fundamental addition. It’s more difficult because it is more mundane. We don’t acknowledge the same need to explain a more simple concept.

Addition.

Same numbers.

-first, can you add them (really? it’s 5 don’t waste my time)

-second, can you tell me why it is so?

Yeah, sure its 5 ’cause you take 2, add another 3 and it’s 5. Of course this is not an explanation. It’s a re statement of the work you did to get the answer. If you want a few $10 words, it is circular reasoning in axiomatic process; it uses a statement to prove itself (though my fellow physicists sometimes have no problem with doing the same thing and just calling it ‘bootstrapping’ i.e. ‘pulling yourself up by your own bootstraps’). If you were paying attention to e.g. earlier, i.e. abbreviates id est. Latin for ‘that is’. With enough time and false starts you may eventually be able to explain why addition works that way. You would have to get to something number theory calls the basic counting principle and fundamental set theory, though most normal people don’t think in such fancy terminology.

My theory on primes basically says, we think primes are ‘up here’ somewhere, but I say they are way ‘down here’, near the bottom, and thus very difficult to get at their foundation.

All texts I have read, when defining what a prime is and/or how to find them, give a process similar to the Sieve of Eratosthones. Mine also follows this model with one important distinction. The general model to test a number for primality is as follows:

Pick your number to test, call it n. Consider that it is a candidate for primality. We haven’t yet proven its is, haven’t yet proven it isn’t, it’s just a candidate. Begin a process of comparing your integer n to another number, let’s start at 1. Perform the division n/1 not all the way, just enough to see if the result is an integer, then move to the next number. Perform this test using all numbers up to n (later we would learn we don’t even need to go all the way to n, sqrt(n) will do). The test is one to exclude it as a candidate, if the test is ever positive you can stop, it’s not prime. Stated a better way, a prime number is special in that there exist only 2 numbers that allow the test to pass, 1 and the number n, all other numbers cause the test to fail.

This test process, of course requires addition, subtraction, multiplication, division.

My process is similar but without +,-,*,/.

Consider a number n as a candidate for primality. Begin a test process to exclude it. If it survives as a candidate up to a sufficient point then it is prime. So what is the test if not +,-,*,/? The test is related to the fact that a number is prime regardless of base system, that is 11 is prime in binary, octal, base 10, hexadecimal and any other possible base system.

Start by writing out all the numbers 0 through n in the smallest possible base system, 2. Underneath write out the same numbers in base 3, try to line them up like:

0 1 10 11 100 101…

0 1 2 10 11 12…

…

You now have an n by n grid.

Start with the first line. Begin with the left. Look to the right until you’ve exhausted the first digit, the first multi digit number that has a 0 at the end. You would strike it out but it’s the first so it gets amnesty. Cross out all other numbers in this line that end in 0. Proceed to the next line down, base 3. Repeat the same process. By the time you get to all n lines of n numbers if your number remains a candidate then it is prime. You wouldn’t have to go all the way to n, but I haven’t found a way to express sqrt(n) without +,-,*,/ in its axiomatic lineage.

This method is very similar but doesn’t require division, rather a counting process of equal sizes in base 2 to eliminate numbers that we would otherwise described as being divisible by 2, then the same counting process in base 3 etc.

With this method not only the number 1, but also 0 survive as candidates for primality and thus I would call them prime. I have not found a text that specifically calls 1 not prime. Rather, when text books list prime numbers they just start at 2. By the classic definition 0 would not be prime because the quantity 0/0 is indeterminate.

If my conjecture has merit to justify a definition of primality it would explain why theorems concerning primes are so elusive.

Hope I haven’t confused you more than myself, and to borrow a phrase from Kalid, Happy Math!

Just to correct one point: you say “you could even argue that pi (3.14159…) is not irrational in base “pi””. I think this is wrong: the criteria for irrationality is not the infinity of decimal figures when writing in base 10 (or any other), it is the fact that pi is not a “ratio”, i.e. not the result of a division of 2 integer numbers. Hope this helps.

Hi Michel, that’s a great point — you’re right, the formal definition of irrationality isn’t about the decimal sequence, it’s about whether it can be expressed as the ratio of two numbers p/q, as you say. I suppose you could argue (poorly :) ) that pi is not irrational in base pi.

Thanks Arun, I plan on addressing this in an upcoming article also. I don’t yet have a good intuitive understanding of the math involved (just a mechanical one, which I don’t like) but I would love to write about this topic.

Kalid, yes I know I’m right, as a former maths teacher ;-)

Then, I’m sorry but I don’t understand (and I’m a bit surprised, as the rest of you post is fully correct) why you repeat in your comment: “I suppose you could argue (poorly ) that pi is not irrational in base pi.”.

Numbers exist out of their representation. Surely, pi would be represented as “1” in base pi, but the number of decimals (finite/infinite) is not a criteria for rationality: 1/2 and 1/3 are both rational, and the second has infinite decimals in base 10, but finite in e.g. base 3.

Hope this helps.

Oh, I do agree, I was just making a joke in the comment that you “could” argue the point, but it would be a *poor* (i.e. invalid) argument to make.

Appreciate the feedback! :)

No, primes are ‘easy’ to discover; one can tell whether a number with d digits is prime in time polynomial in d. That isn’t practical yet, but other methods are so close to polynomial that it doesn’t matter.

Here’s how you can tell whether an inteher is prime or not. One fact about primes p (other than 2) is that

(Fermat’s little theorem) 2^{p-1} = 1 (mod p). That is, p divides 2^{p-1}-1. 7 divides 63, for example. Similarly, if p is a prime other than 3, p divides 3^{p-1} – 1.

The arithmetic of taking powers doesn’t have to be complicated; you can work ‘modulo p’ in these cases. So, if you want to check n for being prime, then look at 2^{n-1}-1. If n doesn’t divide that, n isn’t ptime. If n does divide it, try 3^{n-1}-1. If n divides that, you have more evidence for n being prime.

Now, some numbers n (called Carmichael numbers) are composite, but n divides a^{n-1}-1 for any a (relatively prime to n). So, that test won’t select only the primes. But variants do a better job.

In the end, you don’t use the Sieve of Eratosthenes to find primes. It’s too slow.

Hi Eric, thanks for the clarification! A better restatement may be that large numbers are still hard to factor into primes (which is more relevant to the security problem than simply determining whether a number is prime or not).

do u hv any tric to simplify theory as well as practical subjects?

A sure shot way to identify whether a given number is prime or not :-

The given number must confirm to the expression (6k+1) OR (6k-1) where k is any integer > 0

e.g.

1)7, is a prime number as it confirms to (6k+1) as ((6)(1) + 1)=7

2)47 is a prime number as it confirms to (6k-1) as ((6)(8) – 1)=47

Any number can in the above way be tested to see if its prime or not!

Just to correct you a little ..

the formula holds true only for prime numbers greater than 3

just a tweak to a fabulous empirical formula

So true so true lolololololololollololololololololololololololololololololololololololololololololololololllolololololololololololololololololololololololololololololololololololololololololololololololololololololllololololololololOlolololololololololololllololololololololololololololololOloloollolololololololOlololol

@Archana: I’m planning on writing about how I approach subjects. At a high level, it’s important to always ask “Why?” and “What problem is this trying to solve?” when learning a new subject. Don’t take things at face value — see what they are trying to accomplish.

@Vivek, Saurabh: Great tip! I didn’t believe it at first but this explanation helped: http://everything2.com/index.pl?node_id=1176369

Basically, every number can be written as (6k, 6k + 1, 6k+2, 6k+3, 6k+4, or 6k+5). 6k is clearly not prime. Items 6k+2 to 6k+4 can be written as 2(3k + 1), 3(2k+1), and 2(3k + 2) and therefore aren’t prime as they’re divisible by 2 or 3.

Only 6k+1 and 6k+5 [i.e. 6k-1 for a larger k] remain as possibilities for prime numbers. Be careful though, just because the two numbers are _possibilities_ doesn’t mean either will prime. For k=141, you get 847 (7*121) and 845 (5*169), so neither answer is prime (try it out ).

Great insight, thanks!

Kalid: are you aware of James McCanney’s book, “Calculate Primes”, for the generation of prime numbers . . . if not, I think you would be interested; book costs about $25 at http://www.jmccanneyscience.com

(great work at “betterexplained”!)

[…] His Another Look at Prime Numbers takes the otherwise for math freaks only topic of these oddly behaving numbers and looks at them from a very different perspective Chemistry. Odd and amusing and likely to stay with you for while. […]

Hi Ned, thanks for the info. I haven’t seen that book, I may add it to the reading list :)

Recently (2002) scientists discovered a deterministic polynomial time (basically it means that the solution is not brute-forced which takes exponential time) equation to determine if a number is a prime or composite: http://primes.utm.edu/prove/prove4_3.html

Primes are really interesting and I’ve been looking into them recently. But I haven’t reached anything conclusive about them.

Hi Dasiciks, that’s pretty cool — I’ll have to take a look. I guess the next step is factoring the number once it’s been determined to be composite. Thanks for the info.

James McCanney is a quack. Don’t bother reading his books, Kalid. See Bad Astronomy. He thinks comets are NOT made of ice, for example (and they are).

There’s also the Miller-Rabin prime test: http://snippets.dzone.com/posts/show/4636

Nice post!

Thanks gordon, interesting link! I like seeing little numerical methods like that ;).

Hi, that was a another good post!..

heres some more stuff for your first example-‘guessing evenness’ .

you could also analyze even and odd powers in this manner ….

odd^odd -> odd (There are no 2s at all)

even^even -> even (Lots of 2s!)

even^odd -> even (We are just multiplying even numbers with even numbers. Its just the number of times they are multiplired that is odd )

odd^even -> odd ( no 2’s at all again )

——-

Primes can also help in finding the total no. of factors in a number and their sum …

e.g. 12 = 2^2*3

to get all factors.. write this as

(2^0 + 2^1 + 2^2)(3^0 + 3^1)

= 1 + 2 + 4 + 3 + 6 + 12

sum = 28

no. of factors = 6.

notice that the number of factors is just the number of terms in the expansion…

so if you see a number as a^m * b^n with ‘a’ and ‘b’ being prime, then the number of prime factors is simply (1+m)*(1+n)

:)

@Aaron: Thanks for the comment (I just fixed up the groups)! Actually, I had wondered about that myself — I faintly remember chemistry from school, and never had a proper organic chemistry class, so it’s nice to have these ideas run by someone in the field. I enjoy finding these analogies as they pop up. Thanks again for the notes.

Your last link is dead.

Thanks Ryan, I just fixed it.

Hi, if anyone looks for a good algorithm to display any number by multiply prime numbers (recursive):

**********

code start

**********

void numWays(int num)

{

if ((num%2!=0) && (num%3!=0)){ // This is the simplest event and that means that the number is prime!

if (num!=1) cout