MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm fascinated by prime numbers, and over the years, I've found multiple applications and natural occurrences for them. But can anyone suggest some alternatives that aren't in my list?

Applications of Prime Numbers

  • Public key cryptography algorithms
  • The lengths of hash tables (not recommended)
  • Prime polynomials can be used for hash functions and CRC algorithms
  • Programs that search for large prime numbers can be used as “torture tests” for compilers, multitasking operating systems, memory, processors, etc.
  • Pseudo-random-number generators
  • Hard disk interleaving
  • Error-correction codes (quadratic residue codes)
  • Since no known natural process generates prime numbers, extraterrestrials might use them at the beginning of a radio transmission so we can distinguish it from a natural process (as in Carl Sagan's Contact).
  • Generating organically tiling images

Applications of Coprimality

  • If the number of teeth on a sprocket and the number of links in a chain are coprime, then the sprocket-chain system will experience even wear (cyclical wear will be minimized).
  • Nanotech symmetrical sleeve bearings, in which the outer sleeve has m-fold rotational symmetry and the inner sleeve has n-fold rotational symmetry, would in theory function most smoothly when m and n are coprime. (Nanosystems, K. Eric Drexler, p. 286)

Natural Occurrences of Prime Numbers

  • The 13- and 17-year life cycles of periodical cicadas (genus magicicada) may be an evolutionary advantage (minimizing exposure to predators and competing broods).
share|cite|improve this question
Feel free to leave comments suggesting tags -- for now the moderators are happy to retag as necessary. – Scott Morrison Oct 18 '09 at 3:37
Community wiki? – Anweshi Aug 3 '10 at 13:48

There is a class of error-correcting codes called quadratic residue codes - these are based on the quadratic residues modulo a prime.

share|cite|improve this answer
Thanks, I've added it. – user618 Aug 4 '10 at 19:01
The quadratic residue codes include the perfect ternary and binary Golay codes, which provide points of entry to the realm of the sporadic groups... – DavidLHarden Apr 9 '11 at 7:38

For a semi-serious application of prime numbers, how about "establishing communication with aliens"? See Carl Sagan's novel "Contact".

share|cite|improve this answer
Heh, I think both Carl Sagan and Arthur C. Clarke made mention of alien communication. Added. :) – user618 Aug 4 '10 at 19:04

I hate to say this, but the Yan et al. paper seems a bit crackpotty. (abstract, brief discussion at Google Books from the book by Crandall and Pomerance.) I suspect it's just based on some numerical coincidences.

The others are nice examples, though.

share|cite|improve this answer
Thanks for your comment; I've removed that bad example. – user618 Aug 4 '10 at 18:59

this is somewhat related (but different) to pseudo-random number generators (PRNGs):

The $s$-dimensional Halton sequence is a quasi-Monte Carlo sequence which is a collection of van der Corput sequences in bases $\{b_{1}, b_{2}, \ldots, b_{s}\}$. The bases $b_{i}$ are chosen so that they are pairwise mutually prime. Thus, the natural choice is to use the first $s$ prime numbers.

Quasi-Monte Carlo sequences are number-theoretic sequences designed to give good uniformity in the $s$-dimensional cube. There are randomization techniques which allow them to be to used in simulation like one would with regular PRNGs.

share|cite|improve this answer

The lengths of hash tables

This is something of a myth. If you have a good hash function, the number-theoretical properties of your table's modulus are irrelevant; conversely, if you have a bad hash function, a prime modulus does little to salvage it.

Indeed, a power-of-two modulus has a lot to recommend itself in practice: you can perform reduction of $x$ modulo a power of two $n$ in one processor cycle using the identity $x\ MOD\ n = x\ AND\ (n-1)$.

Look at the highest-performing hash table implementations and you will find they use powers of two. Examples include Google's sparsehash and Sean Barrett's hash table from his article on Judy arrays.

share|cite|improve this answer
I've added a "not recommended" comment at the end of that example, thanks. – user618 Aug 4 '10 at 19:03

Maybe this one is too frivolous, but sometimes, at Chinese restaurants, I get 5 shumai or 7 peking ravioli, instead of 6 or 8, and I've always wondered if that was a deliberate ploy to entice people to order more servings!

share|cite|improve this answer
I remember ordering appetizers at several restaurants that couldn't be divided evenly... – user618 Aug 7 '10 at 21:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.