# Their Fundamental Nature

a whole number that can only be divided without a remainder by itself and one.

Prime numbers are the building blocks of all numbers greater than 1. That is, every number is either itself a prime, such as 2,17,53 or 673, or is the product of primes, such as 17,119 (17 x 19 x 53). Furthermore, every number can be broken up into its primes in only one way. This is no mere supposition: in 1801 the mathematician **Carl Gauss** gave a proof of this “Fundamental Theorem of Arithmetic” (though it seems likely that Euclid had a proof of it 2,000 years earlier).

Beyond their fundamental nature, primes tantalize mathematicians with properties that seem to be true but defy proof. For example, **Euclid** himself came up with a wonderfully neat proof that there is an infinite number of primes, yet to this day no one has proved that there is an infinitude of “prime pairs”, such as 5 and 7 or 59 and 61, in which two consecutive odd numbers are primes.

Then there is **Goldbach’s Conjecture**, first pointed out in 1742, which states that every number greater than 5 is a unique sum of just three primes. Again, while this is widely believed to be true, no one has ever succeeded in proving it.

# Numbers, Games and Pastimes

Proving that a given number is prime has long been used to demonstrate calculating prowess. Once performed by “savants” with a gift for mental calculation, the task was among the first given to electronic computers. The current record for the largest known prime is 2^{43,112,609}– 1. It was found by electrical engineer Hans-Michael Elvenich on 6 Sept. 2008. It has 12,978,189 digits and was discovered using a network of thousands of linked home computers. (see our article To Surf and Serve)

Since the late 1970s, primes have become of enormous commercial importance, as they form the heart of the RSA encryption system, widely used to protect financial transactions.

Roughly speaking, the RSA system is based on the belief that there is no quick way to factorize big numbers into two similarly-sized prime numbers. While many think this is true, yet again a solid proof is lacking. Given what’s at stake, I find this rather disconcerting – equivalent to a bank declaring it’s pretty sure no one will find the mat under which it has put the keys to the safe.

All Prime Numbers up to 1,000 | |||||||||
---|---|---|---|---|---|---|---|---|---|

2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | |

29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 |

71 | 73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 | 109 |

113 | 127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 | 167 |

173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 |

229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 |

281 | 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 |

349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 |

409 | 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 |

463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 |

541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 | 599 |

601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 |

659 | 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 |

733 | 739 | 743 | 751 | 757 | 761 | 769 | 773 | 787 | 797 |

809 | 811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 |

863 | 877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 | 937 |

941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |