# Prime number/Citable Version

A **prime number** is a whole number that can be evenly divided by exactly two numbers, namely 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and 17. In particular, a prime number cannot be factored as the product of two numbers , except for the "boring" factorizations that all numbers possess.

With the exception of 2, all prime numbers are odd numbers, but not every odd number is prime. For example, and , so neither 9 nor 15 is prime. By the strict mathematical definition, the number 1 is not considered to be prime (although this is a matter of definition, and mathematicians in the past often did consider 1 to be a prime).

The importance of prime numbers in arithmetic comes in large part from the unique factorization of numbers. Every number can be written as a product of prime factors, and any two such expressions for will differ only in the order of the factors. For example, we can write , where all of the factors in the product are prime numbers; there is no other way of writing 5040 as a product of prime numbers except by rearranging the prime factors we already have, such as . Because of the unique factorization of numbers into prime numbers, an analogy can be made between the role prime numbers play in arithmetic and the role atoms play in chemistry.

The study of prime numbers has a long history, going back to ancient times, and it remains an active part of number theory (a branch of mathematics) today. It is commonly believed that the study of prime numbers is an interesting, but not terribly useful, area of mathematical research. While this used to be the case, the theory of prime numbers has important applications now. Understanding properties of prime numbers and their generalizations is essential to modern cryptography - in particular to public key ciphers that are crucial to Internet commerce, wireless networks, and, of course, military applications. Less well-known is that other computer algorithms also depend on properties of prime numbers.

## Contents

## There are infinitely many primes

One basic fact about the prime numbers is that there are infinitely many of them. In other words, the list of prime numbers 2, 3, 5, 7, 11, 13, 17, ... doesn't ever stop. There are a number of ways of showing that there are infinitely many primes, but one of the oldest and most familiar proofs goes back go Euclid.

Euclid's proof is a proof by contradiction. Suppose the set of prime numbers is finite, say . Then the number

presents a problem. On one hand, the number is a multiple of , and multiples of the same prime number are never next to each other, so itself can't be a multiple of . The same argument actually shows that itself can't be a multiple of any of the prime numbers , , , ..., . On the other hand, every number is divisible by *some* prime (in fact, it factors completely into prime numbers, due to unique factorization).

This contradiction is irreconcilable unless we admit that our set of prime numbers wasn't complete after all. Since no finite set of prime numbers can be complete, we conclude that there really are infinitely many prime numbers.

While most other proofs of the infinitude of prime numbers are more complicated, they can also provide more information. One mathematical milestone known as the Prime Number Theorem estimates how many of the numbers between 1 and are prime numbers (see below).

## Locating primes

How can we tell which numbers are prime and which are not? It is sometimes possible to tell that a number is *not* prime by looking at its digits: for example, any number whose last digit is even is divisble by 2, and any number ending with 5 or 0 is divisible by 5. Therefore, except for the prime numbers 2 and 5, any prime number must end with the digit 1, 3, 7, or 9. This check can be used to rule out the possibility of a randomly chosen number being prime more than half of the time, but numbers that end with 1, 3, 7, or 9 often have divisors that are harder to spot.

To find large prime numbers, we must use a systematic procedure — an *algorithm*. Nowadays, prime-finding calculations are performed by computers, often using very complicated algorithms, but there are simple algorithms that can be carried out by hand if the numbers are small. In fact, the simplest methods for locating prime numbers are some of the oldest algorithms, known since antiquity. Two classical algorithms are called *trial division* and the *sieve of Eratosthenes*.

### Trial division

*Trial division* consists of systematically searching the list of numbers 2, 3, ..., for a divisor; if none is found, the number is prime. If *n* has a small divisor, we can quit as soon as we've found it, but in the worst case — if *n* is prime — we have to test all numbers to be sure. This algorithm can be improved by realizing the following: if *n* has a divisor *a* that is larger than , there must be another divisor *b* that is *smaller* than . Thus, it is sufficient to look for a divisor up to . This makes a significant difference: for example, we only need to try dividing by 2, 3, ..., 31 to verify that 997 is prime, rather than all the numbers 2, 3, ..., 996. Trial division might be described as follows using pseudocode:

**Algorithm: trial division**

- Given ,
- For each = 2, 3, ... less than or equal to :
- If divides :
- Return " is not prime"

- Else:
- Continue with the next

- If divides :
- When all have been checked:
- Return " is prime"

### Sieve of Eratosthenes

The Sieve of Eratosthenes not only provides a method for *testing* a number to see if it is prime, but also for *enumerating* the (infinite) set of prime numbers. The idea of the method to write down a list of numbers starting from 2 ranging up to some limit, say

- 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

The first number (2) is prime, so we mark it, and cross out all of its multiples

**2**, 3,~~4~~, 5,~~6~~, 7,~~8~~, 9,~~10~~, 11,~~12~~, 13,~~14~~, 15,~~16~~, 17,~~18~~, 19,~~20~~

The smallest unmarked number is 3, so we mark it and cross out all its multiples (some of which may already have been crossed out)

**2**,**3**,~~4~~, 5,~~6~~, 7,~~8~~,~~9~~,~~10~~, 11,~~12~~, 13,~~14~~,~~15~~,~~16~~, 17,~~18~~, 19,~~20~~

The smallest unmarked number (5) is the next prime, so we mark it and cross out all of its multiples

**2**,**3**,~~4~~,**5**,~~6~~, 7,~~8~~,~~9~~,~~10~~, 11,~~12~~, 13,~~14~~,~~15~~,~~16~~, 17,~~18~~, 19,~~20~~

Notice that there are no multiples of 5 that haven't already been crossed out, but that doesn't matter at this stage. Proceeding as before, we add 7, 11, 13, 17 and 19 to our list of primes

**2**,**3**,~~4~~,**5**,~~6~~,**7**,~~8~~,~~9~~,~~10~~,**11**,~~12~~,**13**,~~14~~,~~15~~,~~16~~,**17**,~~18~~,**19**,~~20~~

We have now found all prime numbers up to 20.

## Distribution of prime numbers

*It is evident that the prime numbers are randomly distributed but, unfortunately, we don't know what 'random' means.* - R. C. Vaughan

The list of prime numbers suggests that they thin out the further you go: 44% of the one-digit numbers are prime, but only 23% of the two-digit numbers and 16% of the three-digit numbers. The trial division method explained above provides an intuitive explanation. To test whether a number is prime, you have to try whether it can be divided by all numbers between 2 and . Large numbers have to undergo more tests, so fewer of them will be prime.

The Prime Number Theorem explains how fast the prime numbers thin out. It says that if you are looking around the number , about one in every numbers is prime (here, denotes the natural logarithm of ). The formal statement of the prime number theorem is

where is the number of primes .

## Some unsolved problems

There are many unsolved problems concerning prime numbers. A few such problems (posed as conjectures) are:

### The twin prime conjecture

**Twin primes** are pairs of prime numbers differing by 2. Examples of twin primes include 5 and 7, 11 and 13, and 41 and 43. The *Twin Prime Conjecture* states that there are an infinite number of these pairs. It remains unproven.

### The Goldbach conjecture

The **Goldbach conjecture** is that every even number greater than 2 can be expressed as the sum of two primes. For example, if you choose the even number 48, you can find where 41 and 7 are prime numbers.

### Primes of special forms

- It is not known whether there are infinitely many primes of the form (called Mersenne primes). These primes arise in the study of perfect numbers, and factors of numbers of the form (sometimes called 'Mersenne numbers') are a fruitful source of large prime numbers.
- It is not known whether there are infinitely many primes of the form (called 'Fermat primes'). Fermat primes arise in elementary geometry because if is a Fermat prime, it is possible to construct a regular -gon with a ruler and compass. In particular, it is possible to construct a regular 17 sided polygon (or 17-gon, for short) with a ruler and compass.
- It is not known whether there are infinitely many primes of the form .

## Alternative definition

A prime number is usually defined as a positive integer other than 1 that is (evenly) divisible only by 1 and itself.

There is another way of defining prime numbers, and that is that a number is prime if whenever it divides the product of two numbers, it must divide one of those numbers. A nonexample (if you will) is that 4 divides 12 (i.e. is a factor of 12), but 4 does not divide 2 and 4 does not divide 6 even though 12 is 2 times 6. This means that 4 is *not* a prime number. We may express this second possible definition in mathematical notation as follows: A number (natural number) is prime if for any such that (read *p* divides *ab*), either or .

If the first characterization of prime numbers is taken as the definition, the second is derived from it as a theorem, and *vice versa*. The equivalence of these two definitions (in the integers ) is not immediately obvious. In fact, it is a significant result.^{[1]}

## References and notes

- ↑ The Euclidean algorithm may be used to show that is a principal ideal domain, and this implies that irreducibles are prime.

## Further reading

- Apostol, Tom M. (1976).
*Introduction to Analytic Number Theory*. Springer-Verlag. ISBN 0-387-90163-9. - Ribenboim, Paulo (2004).
*The Little Book of Bigger Primes*, second edition. Springer-Verlag. ISBN 0-387-20169-6. - Scharlau, Winfried; Hans Opolka (1985).
*From Fermat to Minkowski: Lectures on the Theory of Numbers and its Historical Development*. Springer-Verlag. ISBN 0-387-90942-7.

(Note that Scharlau and Opolka was originally published as: Scharlau, Winfried; Hans Opolka (1980). *Von Fermat bis Minkowski: Eine Vorlesung über Zahlentheorie und ihre Entwicklung*. Springer-Verlag. ).