## Primes

*Posted June 2003.*

**1. Introduction**

Numbers are the most common association that people make with the word "mathematics." Numbers are the first introduction to mathematics that children are exposed to, perhaps along with some geometry. Children learn to count early and number books are very popular with children. New titles are appearing all the time. "Clever-Hans" aside, counting and working with numbers seem to be uniquely human activities. To the best of our knowledge non-human animals (and plants) do not put counting to systematic use.

The branch of mathematics that is concerned with the properties of numbers for their own sake is called number theory. Number theory has a long history. One of the milestones in that history can be found in a book that we associate with geometry: Euclid's*Elements*. In Book IX, Proposition 20 of *The Elements* we find a proof, stated in modern language, that there are infinitely many primes. (*The Elements* also contains another gem of number theory: A treatment of what is today known as the "Euclidean algorithm," which is concerned with finding the largest number which will divide each of two numbers, better known to students as finding the greatest common divisor.)

It is truly remarkable that over 2000 years ago human thought had identified that the numbers now known as primes play a special role in the structure of the number system. What is a prime number? A *prime number* is a positive integer which is at least 2 and whose only divisors are one and the number itself. For example, 31 is a prime because the only positive numbers that divide 31 are 1 and 31. The number 60 is a *composite* *number*, that is, a number which can be written as a product where none of the factors is 60. Thus, 60 is not a prime because it can be written as 6 x 10 or 5 x 12.

It might seem as if there is not a lot to say about prime numbers, but nothing could be further from the truth. New insights about the primes are arrived at on a regular basis, but very recently a dazzling new insight about primes (discussed in Section 6) was obtained.

*Joseph Malkevitch*

York College (CUNY)

Email: malkevitch@york.cuny.edu

*Introduction*
*Basic ideas*
*Distribution of the primes*
*Complexity and algorithms*
*Primes and cryptography*
*The right stuff*
*References*

Welcome to the
Feature Column!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.

Read more . . .

Feature Column at a glance