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 = 32
- 12 = 2 * 2 * 3 = 22 3
- 100 = 4 * 25 = 2 * 2 * 5 * 5 = 22 52
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 H20:
- Water = H20 = two hydrogens and one oxygen
And for a number, we can break it into primes
- 12 = 2 * 2 * 3 = 22 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 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 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.
RSS
31 Comments »
Trackbacks & Pingbacks
-
Pingback by magpie’s shiny things»Blog Archive » Ready- Better Explained - This is what the web can be. — November 29, 2007 @ 11:22 am
-
Pingback by Better Explained « Xavier Seton’s Blog — May 7, 2009 @ 12:35 am
Comments
RSS feed for comments on this post. TrackBack URI
Leave a comment
Have a question? Know an explanation that caused your own a-ha moment? Write about it here.
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.
Michel — September 10, 2007 @ 12:07 am
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
arun — September 10, 2007 @ 11:00 am
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 — September 10, 2007 @ 11:10 am
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.
Michel — September 21, 2007 @ 3:25 am
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!
Kalid — September 21, 2007 @ 9:07 am
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.
Eric Jablow — October 2, 2007 @ 2:03 pm
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).
Kalid — October 2, 2007 @ 4:29 pm
do u hv any tric to simplify theory as well as practical subjects?
Archana — November 13, 2007 @ 5:11 am
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!
Vivek Zaveri — November 13, 2007 @ 7:31 am
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
Saurabh Sonparote — November 13, 2007 @ 9:56 am
@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 — November 13, 2007 @ 2:52 pm
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”!)
Ned Lee — November 14, 2007 @ 7:54 am
Hi Ned, thanks for the info. I haven’t seen that book, I may add it to the reading list
Kalid — November 29, 2007 @ 11:33 am
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.
dasickis — December 4, 2007 @ 11:11 am
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.
Kalid — December 5, 2007 @ 4:47 pm
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).
Brian — February 28, 2008 @ 8:13 pm
There’s also the Miller-Rabin prime test: http://snippets.dzone.com/posts/show/4636
Nice post!
gordon — April 15, 2008 @ 11:41 am
Thanks gordon, interesting link! I like seeing little numerical methods like that
.
Kalid — April 15, 2008 @ 3:01 pm
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)
anac7ronox — May 27, 2008 @ 4:47 am
Nice as always, Kalid -
I have a tiny nitpick, only because I’m a chem major — the noble gases aren’t in group “18″ they are in Group 8A. Carbon / Silicon are in Group 4A.
The reason this is important is due to valence shells (an elements group #, from the “A-Series” indicates the number of electrons in its outermost, or valence, shell). The B-Series (aka “transition metals”) are more or less completely irrelevant in an organic context.
I did like your analogy to functional groups though — that’s a neat way to think about it. FG’s are generally expressed, formulaically as “R-OH” [alcohol] or “R-COOH” [carboxylic acid] implying that the R-group is unimportant / non-reactive.
In your example, the R-group would be whatever is added to the functional portion. So the 2 * 5 F.G. could be expressed, in an O-Chem context, as R(2*5).
Anyways… enough of my anal-retentiveness — very cool, as always.
Aaron — August 11, 2008 @ 8:19 pm
@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.
Kalid — August 11, 2008 @ 11:19 pm
Your last link is dead.
Ryan Scott Scheel — August 24, 2008 @ 12:02 am
Thanks Ryan, I just fixed it.
Kalid — August 24, 2008 @ 12:54 pm
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
Shir (Israel) — January 3, 2009 @ 5:52 am
As a high school student desperately attempting to approach math as an acadamic subject as opposed to a scary monster, I’d like to thank you for this article. It’s really made prime numbers seem much more friendly than before. =)
mike — February 15, 2009 @ 7:51 pm
@Shir: You need to be careful — try it with 25
@Mike: Glad you enjoyed it!
Kalid — February 17, 2009 @ 12:33 am
hi I m looking for parallel algoriths.
and a problem solve by using parallel algorith.
umabdu — April 9, 2009 @ 3:56 am
Also, small addition here.
Any number with a 3 can have its digits tallied and they will also be divisible by 3. For example, 141 (47*3) = 1+4+1 = 6, also 196605 (65535*3) = 1+9+6+6+0+5 = 10+12+5 = 27 = 2+7 = 9. Etc.
Thank you for setting this site up. I have never studied Calculus, always considered it the Devil’s answer to real thought. Now I am heading back to school to get my degree in programming, and have found this site fantastic.
Many many thanks.
Steve — May 29, 2009 @ 9:52 pm
@Steve: Awesome, glad it is coming in handy! Yes, I like that trick about the digits adding up.
Kalid — May 30, 2009 @ 3:48 am