Is there anything particularly relevant about prime numbers? They seem to get a lot of attention and I never understood why.
They sure are relevant to mathematicians (and computer scientists, etc.) Do you mean more “natural” applications? For example, there is a cicada known to emerge in prime-numbered year cycles as an evolutionary strategy (predator avoidance).
They’re useful in cryptography, particularly the products of very large primes. Those products, since they only have 4 factors (1 and themselves, as well as the 2 very large primes used to construct the number), are very difficult and time-consuming to factor, even for computers, and so are useful for encrypting and decrypting.
One of the more common applications (though most people using it don’t understand or need to care about the mechanics) is RSA cryptography, allowing a person to send secret messages. The gist (highly simplified) is that:
Secretly choose a prime number p, which by definition can only be divided by 1 and p itself.
Secretly choose a different prime number q, which by definition can only be divided by 1 and q itself.
Multiply p and q to get N. N, therefore, will only be divisible by 1, p, q and N itself.
What allows RSA cryptography to work is that once you’ve chosen p and q, generating N is easy. If all you have is N, trying to work backward to find p and q is difficult.
Picture 15. Very quickly, anyone can see that its p and q are 5 and 3. But what if N is 927401749817398759182759192911 ? How long would it take even a very fast computer to find p and q? Years? Centuries? The age of the universe?
Anyone can generate their own N and publish it freely. This becomes their “public key”. If I wish to send a secret message to someone, I will use their public key to encrypt it. Then it doesn’t matter who might see the encoded message, because the only way to decrypt it is by using p and q, which the recipient knows and has not published, as they form his “private key”.
With the cryptography applications mentioned, it is also to be said that math guys love prime numbers for the same reason climbers like mountains. They are challenging to get to.
927401749817398759182759192911 = 11 x 13693 x 6157105819279915810883857
Okay, that was pretty quick.
Public keys involve numbers that don’t have small divisors (like 11 and 13693), for just that reason
“Relevant” to what or to whom?
Prime numbers are the building blocks of all (whole) numbers, in somewhat the same way that the chemical elements are the building blocks of all chemical compounds.
Water is H[sub]2[/sub]O, and salt is NaCl.
10 is 2*5, and 24 is 2[sup]3[/sup]*3.
(And because 10 = 2*5 is the basis for our base-10 numbering system, the fractions that have terminating decimal representations have denominators whose only prime factors are 2 and/or 5. If the denominator has any other prime factor besides 2 or 5, it’s a repeating decimal. That’s just one of the many ways in which primes are relevant to the way numbers “work.”)
Another common use of prime numbers in computing is in hashing.
Hashing is when you take a long string of something meaningful (a name, a part number, whatever you’re keeping track of and want to access quickly) and use a function to map it into a small range.
So you want to keep track of a thousand parts with really long part numbers. Keep them in a table a bit over a thousand places long. Someone types in a part number, apply the hash function to get where it (hopefully) is in the table. Look for it there. (There’s strategies for dealing with two things mapping to the same place.)
One common aspect of picking the size of the hash table is to make it a prime number. This makes things like the aforesaid double mapping issue easier to deal with. Pick a k. If the hash maps to m, look there, if it’s not there look at m+k, m+2k, etc. until you find it (or hit a blank spot in which case it’s not in the table). A properly chosen hash function, table size, etc. means you don’t have to look far. But in the worse case you keep looking and looking until you look everywhere.
If the table size wasn’t prime, you might loop around the same spots over and over. E.g., a table size 20 and k of 5 you look at 3, 8, 13, 18, 3 …
There is an astonishing number of ways that using primes in computing that ensures that things get distributed right, even balanced, etc.
The classic Fast Fourier Transform uses large powers of two but creates certain artifacts since those powers of two are quite non-prime. (In a FFT processed image of an asteroid you may see “ghost” dots around it.) There’s an algorithm by Al Borodin that’s almost as fast and uses large primes. Eliminates many artifacts.
All this of course reminds me of the Number Theorist G.H. Hardy’s quote: “No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years.”
That was 1940. Number Theory was already being used in breaking enemy codes and relativity led to the Bomb.
Don’t knock something if it seems impractical. Uses are found quite often.
Sorry, I meant to say 9274017498173987591827591929119287549275972957923857293579287562936729375290375293759235879238750298672098672395723957293875923857926729367829867296872967.
That’s only 154 digits. I think such numbers can now be factored, although not easily. But the product of two 500 digit primes will be essentially unfactorable, at least without a quantum computer.
One interesting fact is that there are algorithms that can quickly test to see if a 500 digit prime with 99.9999999…% probability. There are also much slower ones that give 100% but I doubt they are worth the effort. This is what makes RSA encryption so successful.
It’s also clearly divisible by 3343 
But, yes, it gets harder: to generate good RSA moduli you can start out by randomly choosing two (sufficiently) large primes- 500 digits is not overkill here- and multiplying them together.
The Ishango bone is 20,000 years old and has a row of tally marks representing 11, 13, 17, and 19, the four primes between ten and twenty. It has been speculated that it was useful to decide if a collection of objects could be evenly divided. Anyway, who ever made it found those numbers interesting enough to write down.
Really? You think that was needed to determine whether a set of 19 or less objects could be evenly divided?
Obviously I’ve been ninja’ed, but my old laptop factors this tiny number in a tiny fraction of a second!
Yes. BTW, sometimes “quadratic reprobing” is useful (m, m+1, m+4, m+9, …) although it visits only half the table.
Another use of prime numbers is in reversible hashing, for example:
hashc = datum * 2340563 % 3787109
datum = hashc * 3749658 % 3787109
(The first two constants are primes.)
Finally, may I plug Good Thief, one of my favorite movies?
Bob (Nick Nolte) places a large bet on 17. Anne (Nutsa Kukhianidze) pushes the stack to 18, saying “It’s my birthday. I’m not a prime anymore.” (Not only does the roulette ball land on #18 but, although Bob is still much older than Anne, the age of 18 offers some legitimacy and the viewer senses that the sexual tension between the two need no longer go unrequited.)
For a loosely related reason, it is often good practice to arrange that the number of teeth on two interacting gears be relatively prime to each other.
Prime numbers: 1,2,3,5,7,11,13…
Prime ribs: in packs of 3,5,7,11…
Coincidence?
The largest Prime Rib number is 7. All the numbers 1 - 7 are Prime Rib numbers. I do not know if they are related concepts, I know meat pretty well, but math not so much.
3343 × 80814362767 × 34327563689566697334089737489352304622626569537285926010522105474112102391286515036197395301245419504370957964659993730648 90549347575330407 (or at least that’s what the online factor site is telling me.)
ETA: Oh, wait, that latter number is continuing to break down as I let it run, so it’s not a complete prime factorization. Oh well.