# 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 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 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 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.

• 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 "33" functional group. A number could have 400 threes, but as long as there's at least 2 we're interested. If a number has (33) 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.

## Questions & Contributions

1. Michel says:

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.

2. arun says:

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

3. Kalid says:

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.

4. Michel says:

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.

5. 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!

6. Eric Jablow says:

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.

7. Kalid says:

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).

8. Archana says:

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

9. 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!

10. Saurabh Sonparote says:

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

11. Kalid says:

@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!

12. Ned Lee says:

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”!) 13. Kalid says: Hi Ned, thanks for the info. I haven’t seen that book, I may add it to the reading list 14. dasickis says: 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. 15. 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. 16. Brian says: 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). 17. Kalid says: Thanks gordon, interesting link! I like seeing little numerical methods like that ;). 18. anac7ronox says: 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) 19. 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. 20. Kalid says: @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. 21. Ryan Scott Scheel says: Your last link is dead. 22. Kalid says: Thanks Ryan, I just fixed it. 23. Shir (Israel) says: 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 24. mike says: 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. =) 25. @Shir: You need to be careful — try it with 25 @Mike: Glad you enjoyed it! 26. umabdu says: hi I m looking for parallel algoriths. and a problem solve by using parallel algorith. 27. Steve says: 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. 28. @Steve: Awesome, glad it is coming in handy! Yes, I like that trick about the digits adding up. 29. Lisa says: Thank you so much for making this site. It really made primes a lot easier. I’m doing a report on them (due this monday i’m afraid). It made them seem like they had a purpose and explained a lot. 30. Kalid says: @Lisa: You’re welcome, I’m glad it was helpful for you. Good luck with your report! 31. Al says: hey mate, (Guessing evenness) you say that to quote “Odd times odd is odd. We never put in a 2 the whole time, so we stay odd.” but what about 3×3= 6 EVEN 32. Kalid says: @Al: Make sure you double check that 3×3 :). 33. Mikel Greathouse says: Hi yeah all it is Me Nobody and I painted the table for you all and let Me tell you you are just going to pee your self when you see it. Mind boggling I must say. So many of you are so close if it was a snake he has his fang up against your skin and is ready to bite. That guy with the 12 block Idea now he has been bitten already and the Hope mathematics people with there 180 system ,look out for them for they are getting bitten hard. 34. Donna Muhammad says: I really appreciate your article. I was searching for a way to make primes relevant to my 4th & 5th graders, not just naming them, so I am exceptionally interested in the aspect of relating it to nature and the cycles of nature. I will focus my studies in that direction for know and would love to have any more info you have on prime cycles in nature — saving me slogging through the animal kingdom, plant kingdom, etc.. 35. The sequence of the prime numbers has not been explained yet. True, but let’s claasify them logically. The number two [2] is in one class by itself and the numbers [3, 5, 7, 11, … ] are in another categorically distinct class having an infinite number of members. I want to share an insight that recently occurred to me. The distribution rules of elementary algebra universally apply to multiplication over addition and subtraction. That gives us two rules. The other rule: the distribution of addition and subtraction over multiplication is generally untrue. The word ” Generally ” differentiates this situation from universally or categorically untrue. The assertion is that the latter rule is true – sometimes. Allowing addition and subtraction to be distributive over multiplication brings into existence relationships between the algebraic variables. This may prove to lead to very interesting consequences where the four rules of distribution are true altogether. Especially where the algbraic variables are uneven integers. 36. Futher to my comment above,I am convinced that the mystery of the sequence of the Primes [prime numbers] can be explained [within elementary algebra] fairly easily. But first we must take a more careful look at the rules of distribution: To save writing, let’s put A = addition, S = subtraction, M = multiplication. Now let us assert that the following four rules are true – simultaneously. [a] A is distributive over M [b] S is distibutive over M [c] M is distributive over A [d] M is distributive over S This implies [necessitates] that there exist intrinsic relationships among the algebraic variables – equations [because all the four rules above are valid]. Where rules [a] and [b] fail, this must be regarded as exceptional [there are an infinite number of exceptions]. The above truth of the four rules lead to an algorithm that I have called: The Evolutionary Algorithm. T.E.A is just the kind of algorithm needed to settle this mystery [let’s not call it a mystery, let’s downgrade it to a puzzle – most people like puzzles] of the prime sequence. However one or two details need to be fixed before this algorithm can be started and implemented. [i] being able to solve the pairs of equations that constitute each step of T.E.A. [ii] there are two [fixed] algebraic variables in the first step of T.E.A. whose values need to be assigned. Once this is gotten past then we should have an algorithm that produces the successor prime, one at a time at each step. Then the manner in which sequence of the primes works may be come clearer, if not absolutely clear. You might have guessed why there are two equations in each step of The Evolutionary Algorithm – its because there are two rules of distribution – rules [a] and [b]. I now want to indicate how T.E.A. is constructed. The two simplest equations arising from the rules of distribution are: b.c + a = [b + a].[c + a] rule [a] b.c – a = [b – a].[c – a] rule [b] The rules of commutation and association may be considered to be universally valid. Note the peculiar order in which the terms on the left side of the equations have been written. The above two equations constitute the first step of T.E.A and are easily solved for the variable: a in terms of b and c. The right sides of the two equations are calling to be multiplied out. There are many actual numbers that can be set for b and c, therby giving a value for: a. However suitable values for b and c in T.E.A. have not yet been found. It could be expeditious to concentrate on uneven integers for b and c [perhaps a few early members from the class: [3, 5, 7, 11, 13, …]. It would be better now to introduce notation. The first two equations become: d[1].d[2] + a[1] = [d[1] + a[1]].[d[2] + a[1]] [ – 1]**{2}.[d[1].d[2] – a[1]] = [d[1] – a[1]]. [d[2] – a[1]] The factor involving minus one: [ – 1] is put there for a good purpose – not to make the maths more difficult. In the next step of T.E.A. we set d[3] = a[1], which we just have computed in the first step. Then we relabel a[1] as a[2]. The first equation in the second step is: d[1].d[2].d[3] + a[2] = [d[1] + a[2]].[d[2] + a[2]].[d[3] + a[2]] The second equation in the second step is: [ – 1]**{3}.[d[1].d[2].d[3] – a[2]] = [d[1] – a[2]].[d[2] – a[2]].[d[3] – a[2]] We use the second step to compute a[2] in terms of d[1], d[2] and d[3]. Then we set d[4] = a[2] and relabel a[2] as a[3]. I’ll just write out an abbreviated version of the second equation for the third step. The first equation [involving addition] for the third step is easy to write down. The second equation in the third step is: [ -1]**{4}.[d[1].d[2].d[3].d[4] – a[3]] = [d[1] – a[3]].[d[2] – a[3]].[d[3] – a[3]].[d[4] – a[3]] [not really abbreviated at all] In the step involving a[j] in the second [subtraction] equation, there is a term [ – 1]**{j + 1} to multiply the left side and we are tying to solve for a[j] in terms of the fixed [ assigned] values of d[1] and d[2] in step one and the computed values: d[3], d[4], … d[j + 1] from the a[j – 1] values in the previous steps. The T.E.A. algorithm outlined above uses all of the previous information to find the next piece of information so that the algorithm can be continued one step at a time indefinitely. This is exactly what we need in order to find the sequence of the primes – an algorithm that computes the next prime in the sequence, having used all of the previous primes as input information – once the two hurdles [i] and [ii] have been passed by. Then the sequence can be explained. I have called this basic algoithm: The Evolutionary Algorithm [T.E.A.] because while the multiplicands on the left sides of the equations are fixed in value, once the first two have been assigned [d[1] and d[2] and the others d[3], … d[j + 1] subsequently computed, the actual number of such multiplicands increases indefinitely without limit by one at a time with each sucessive step – hence an evolving [evolutionary] algorithm. The above insights came to me around February 19th 2011. [If anyone has done the same as above before now, then I would certainly like to know abot this.] I do hope that my comment is not too long – William P. G. Shaw. [Februay 25th, 2011]. 37. In comment No. 37 above, I must apologise for a few minor, but I hope obvious errors: a typographical error: on the first line, there should be a space after the comma, then ” I am convinced … and somewhere I wrote ” bot 2. This should surely be ” about ” and ” therby ” should be ” thereby ” and I noticed an extra un-needed space after an opening bracket. Similar comment applies to my comment No. 36. Although I read over my comment as well as I could in the time [and energy] available to me, I tend to get word blind, that is I look at the print but do not always recognize a mistake. [but I did check over the equations very well] – W. P. G. Shaw. 38. My final comment on my comments above is this: to get a better understanding of the infinite [Euclid’ s theorem] series of primes: [3, 5, 7, 11, 13, … ], just imagine if you like, the series printed in say Font No. 12, Times New Roman-[my favourite style], then this series of primes would stretch beyond Pluto to the end of the universe and then beyond that, and never come to an end. Just imagine that. 39. TE says: A bit of a late reply to Arun, but it’s used for cryptography because you can’t get the prime numbers used to encode something. Look at RSA system for the most popular cyptographic system in the world now. A formula takes two different prime numbers and uses them to generate some other numbers. Those other numbers are used to get keys to encrypt and decrypt. If you don’t know those prime numbers, you won’t be able to figure out the keys. Hacking it means that you’ll be trying to “brute force” by testing out every prime number and see if you can get one that generates a key used to decrypt a file. 40. Ryan says: Very nice article and some great comments. I was wondering if anyone knew of any research or insight regarding the square roots of primes. eg do they exhibit certain properties for different primes ie large primes, messerne primes, their distribution, etc. (of course they are all irrational…) It’s strange but I had a dream about the squares of smaller primes displaying more “chaotic” behavior in their decimal expansion (what ever that means, it was a dream!) 41. brittany says: ok these are all great comments..but i think i am over thinking primes…well i am still not understanding them….. ughh…i just wont give up untill i have mastered these or at least come to an understanding of how they work…someone help me please!!! 21 yr old …lost in her textbooks!!! 42. Kalid says: @Ryan: Really interesting question, I don’t know much about the distribution unfortunately @brittany: Here’s another analogy that might help: Each number is a “word” and primes are the “letters” that make it up, assuming we can only multiply. So 100 is made of 10 * 10 = 2 * 5 * 2 * 5. Interestingly, there is an infinite number of primes (“letters”), like an alphabet with an infinite number of letters (imagine chinese… there is no limit to how many symbols they can make :)). It’s not a perfect analogy but it’s another way to see the primes as “building blocks” for other numbers. 43. Excellent Explanation… and so the discussion. 44. kieta says: I’ve been skimming through sites related to math, to prepare for the ACT. I’ve been out of school awhile. With the approach taken on this site I actually enjoy learning about numbers. It’s presented here like a game. 45. One more thing that many find interesting about a cabin themed home decorating plan is the fact it simply exudes temperature year round. From the dark colors towards the flannel materials and this soft homespun simplicity in the design many find it simply irresistible. One thing that is obvious in this style of decorating is the fact it appeals to individuals who love home and fireplace and warmth and good will alot more than modern touches plus design elements. This is not a hard plastic form of design style and it shouldn’t endeavor to become one as both the styles are almost systematically opposed to one another. 46. Huen Yeong Kong says: Please refer to: Development of General Twin-Prime Number System by the Method of Indirect Induction Huen Yeong Kong Pages 1-12 View Details Abstract References Now we have a pure prime number system which could map uniquely into all natural numbers from 2 to infinity without breaks. But the Iconic Symmetrical General Twin-Prime number sytem is actually an object-oriented number system formed by prime-triplets based on the Half-Sum formula. The development shows that consecutive primes does not form a number system. It is the Iconic SGTP number system which reveals in depth how primes interact with the natural number system. 47. Huen Yeong Kong says: Oop, sorry, forgot to specify the journal: Aditi Journal of Computational Mathematics Volume 1 ( 2013 ) , Number 1 huen yeong kong 48. Mike says: Thank you Kalid. For the first time I have glimmering as to why primes are important and unique. Why do primes have to have a pattern? Can’t they simply be random? 49. Eric V says: 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!

50. Anonymous says:

@Ryan

If you’re still reading this after three years, you should listen to to your dreams, the golden door to the unconscious. It makes sense to me t

51. Anonymous says:

@Ryan

As I was saying, it makes sense to me that there may be degrees of randomness, just like there are degrees of infinity. If you worked on it, you could come up with something, or at least be happy with the effort.

52. Ashok Jain says:

Dear Kalid

I have bought your book Maths – better explained , few days back , it is very well explained .All what ever i read was really helpful in either physics or electricals . One thing i need to ask you that this prime number topic is not in book it seems. Please confirm .Also you have published only one book or there are more .please mail me your reply .

Onece again thank you very much for making maths interesting .

53. Anonymous says:

Depite appearances to the contrary, you do not need to know ALL primes up to a point to find the NEXT prime.
Ex. 15 = 3 * 5
To tell that 15 is not prime, you need only know that 15 mod 3 = 0.

Prime P is not needed in checking a range until the first semiprime which consists of primes not in the set of primes before prime P.
This is because, no matter how many primes are multiplied together, the result’s prime factors are ONLY those primes. (11 * 13 = 143. 143 is only divisible by (1, 11, 13, 143))
The first such semiprime is prime P squared, because ANY greater prime S, times prime P, results in a number greater than prime P squared. (5 * 5 = 25.
5 * 7 = 35. 35 > 25)

Thus, to check if the number N the next prime NP, you need only check if N is divisible by at MOST the first prime L to have a square greater than (or equal to) N, and all primes befor prime L.

This is usually done by checking the primes UP TO the square root of the number N.

54. Anonymous says:

After 2, every prime must be ‘odd'; not dividible by two.
any number N times 2 mod 2 = 0
0+1=1
Thus 2n± 1 mod 2 =1, and 1 is not = to 0.
(n is a whole number)

After 2 and 3, every prime must neither be divisible by two or three.
Numbers not divisible by 2 can be represented by 2n± 1.
Numbers not divisible by 3 can be represented by 3n± 1 or 2.

These sets intersect at 6n± 1(or 5), which includes EVERY number not divisible by 2 or 3,
thus everyprime after 2 and 3 is a solution to 6n± 1 or 5.

55. Anonymous says:

This explains Vivek Zaveri ‘s method.

It was originally deduced by analyzing the position of prime in base 12,
where every prime after 2 and 3 is to the left or right of the column of 6’s multiples, which aren’t multiples of 12, similar to the column of 5’s odd multiples in base 10.

0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19

56. Albert Paquette says:

Hi:

I love your site. The absolute best way to teach math is the way you do it.

I didn’t have time to go through all the comments, but I noticed that you didn’t explicitely mention the fundamental theorem of arithmetic, or the unique prime factorization theorem: Every integer greater than one is either a prime or is the product of a unique set of primes.

If I missed it somewhere, my apologies.