This article is an introduction to prime numbers. This includes the fundamental theorem of arithmetic, a test for primality, and a proof that the number of primes are infinite.
Prime numbers have primordial significance in mathematics, and interest in them, since the time of Euclid, has never waned at all. They are still serious objects of professional mathematicians' study today. Let us recall: what is a prime number? A prime number is a positive integer with exactly two factors: 1 and itself. By contrast, composite numbers are positive integers with more than two factors. For instance, 7 is a prime number, because its factors are only 1 and 7. By contrast, 30 is a composite number, because it has more than two factors (which are 1, 2, 3, 5, 6, 10, 15, and 30). The number 1 has one, and only one factor, which is 1, so it is not prime (because it does not have exactly two factors) and not composite (because it does not have more than one factor).
The Fundamental Theorem of Arithmetic
Perhaps the primary significance of primes lies in the fact that they are the building blocks of composite numbers. For instance, 30 = 2•3•5; 200 = 2•2•2•5•5; 660 = 2•2•3•5•11. The fundamental theorem of arithmetic states that every positive integer greater than 1 is either a prime or can be expressed as a product of two primes. The process of breaking down a composite number into its prime factors is called prime factorization, which can be done by either using a factor tree or decomposing the number by continuous division with primes.
A Test for Primality
All prime numbers, except 2, are odd. 2 is the only even prime number. All other even numbers are composite because they have at least one factor aside from 1 and itself: 2. The first ten prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. For small numbers, a sure-fire efficient way of determining whether a number is prime or not is to test whether it is divisible by all primes less than its square root. For example, let us find out whether 313 is a prime. The square root of 313 is about 17.692 (can be determined by calculator – or by noting that 17^2 < 313 < 18^2, so we just have to check all primes less than or equal to 17); all primes that fall below it or are equal to it are 2, 3, 5, 7, 11, 13, 17. We do not have to check anything that falls after. Now, by manual division, we find out that 313 is not divisible by 2, 3, 5, 7, 11, 13, and 17, so we can safely say that 313 is prime.
Let us try 583. Its square root is between 24^2 and 25^2, so we have to test all primes less than or equal to 24, which are 2, 3, 5, 7, 11, 13, 17, 19 and 23. By inspection upon all these possible prime factors, we determine that 11 is a factor (583 = 53•11) so we know that 583 is composite. What is good about this method is that we have to try only those primes less than or equal to the square root of a number – we don’t have to exhaust ourselves by trying anything else. For large prime numbers, however, the method could be painstaking, and there are other more efficient algorithms that could test their primality.
Infinitude of Primes
Now that we know about small primes and large primes, this question strikes us curiously: Is the number of primes infinite? Euclid dealt with that question 2000 years ago, and outlined a proof of this sort: Suppose the number of primes is finite; then it should have a largest prime P. Let N be the product of primes less than or equal to P plus 1; that is,
N = (2 • 3 • 5 • 7• 11 • 13 • 17 • ... • P) + 1
We have these following characteristics about N: (1) N must be a prime, but if that happens, P is not the largest prime, because N > P, or (2) N must have a prime factor larger than P, because when N is divided all primes less than or equal to P, there is a remainder of 1. Once we assume that there is a largest prime, we run into the contradiction that there is a prime larger than the largest prime. Therefore there is no largest prime, and the number of primes must be infinite.
While we know that there is an infinitude of primes, many people are still curious about finding large individual primes. As of today, the largest prime is 2^43112609 – 1 and has 12,978,189 digits. It was found on August 23, 2008 through distributed computing. Prime numbers involve frontiers of mathematics in which many are already known, but where still many are yet to be known, and mathematicians for generations will be willing to throw their entire lives in exploring their properties.