Prime number

A **prime** is a natural number that has exactly two divisors: one and itself. A natural number can be gotten by multiplying two numbers. These two numbers are called its divisors. Any natural number is equal to one times the number itself, so those two numbers are two of its divisors. A prime is a number with _only_ two divisors: one and itself.

The prime numbers are the numbers other than one which are _not_ equal to  (except one times itself). The smallest prime number is two. The next prime numbers are 3, 5, 7, 11, and 13. The set of prime numbers is sometimes written as .

If the number has any other divisors besides one and itself, then the number is called a composite number. The smallest composite number is four, because two times two equals four; thus four has three divisors. One is not a composite number or a prime number because it only has one divisor, one.

The fundamental theorem of arithmetic states that every positive integer can be written as a product of primes in a unique way, though the way the prime numbers occur is a difficult problem for mathematicians. When a number is larger, it is more difficult to know if it is a prime number. One of the answers is the prime number theorem. One of the unsolved problems is Goldbach's conjecture.

There is no largest prime number. One of the most famous mathematicians, Euclid, recorded a proof that there is no largest prime number. However many scientists and mathematicians are still searching to find it as part of the Great Internet Mersenne Prime Search.

## How to find small prime numbers

There is a simple method to find a list of prime numbers. Eratosthenes created it. It has the name Sieve of Eratosthenes. It catches numbers that are not prime (like a sieve), and lets the prime numbers pass through.

The method works with a list of numbers, and a special number called _b_ that changes during the method. As one goes through the method, they circle some numbers in the list and cross out others. Each circled number is prime and each crossed-out number is composite. At the start, all the numbers are plain: not circled and not crossed out.

The method is always the same:

1. On a sheet of paper, write all the whole numbers from two up to the number being tested. Do not write down the number one. Go to the next step.
1. Start with _b_ equal to two. Go to the next step.
1. Circle _b_ in the list. Go to the next step.
1. Starting from _b_, count up _b_ more in the list and cross out that number. Repeat counting up _b_ more numbers and crossing out numbers until the end of the list. Go to the next step.
    - (For example: When _b_ is two, you will circle two and cross out four, six, eight, and so on. When _b_ is three, you will circle three and cross out 6, 9, 12, and so on. 6 and 12 have already been crossed out. Cross them out again.)
1. Increase _b_ by one. Go to the next step.
1. If _b_ has been crossed out, go back to the previous step. If _b_ is a number in the list that has not been crossed out, go to the third step. If _b_ is not in the list, go to the final step.
1. After this point, all of the prime numbers are circled and all of the composite numbers are crossed out.

For example, one could carry out this method on a list of the numbers from 2 to 10. At the end, the numbers two, three, five, and seven will end up circled. These are prime numbers. The numbers 4, 6, 8, 9 and 10 will be crossed out. These are composite numbers.

This method or algorithm takes too long to find very large prime numbers. However, it is less complicated than methods used for very large primes, such as Fermat's primality test (a test to see whether a number is prime or not) and the Miller-Rabin primality test.

## What prime numbers are used for

Prime numbers are very important in mathematics and computer science. Very long numbers are hard to solve. It is difficult to find their prime factors, so most of the time, numbers that are probably prime are used for encryption and secret codes. For example:

- Most people have a bank card, where they can get money from their account using an ATM. This card is protected by a secret access code. Since the code needs to be kept secret, it cannot be stored in cleartext on the card. Encryption is used to store the code in a secret way. This encryption uses multiplications, divisions, and finding remainders of large prime numbers. An algorithm called RSA is often used in practice. It uses the Chinese remainder theorem.

- If someone has a digital signature for their email, encryption is used. This makes sure that no one can fake an email from them. Before signing, a hash value of the message is created. This is then combined with a digital signature to produce a signed message. Methods used are more or less the same as in the first case above.

- Finding the largest known prime number has, over the years, become a sport of sorts. Testing if a number is prime can be difficult if the number is large. The largest primes known at any time are usually Mersenne primes, because the fastest known test for primality is the Lucas-Lehmer test, which relies on the special form of Mersenne numbers.

## Related pages

- Coprime
- List of prime numbers
- Palindromic prime
- Prime factorization
- Wilson prime

## Other websites

- GIMPS, a group that searches for Mersenne primes