# Searching for Prime Numbers

A prime number is any integer that cannot be divided by any integer except itself and one.  A composite number is an integer that has divisors other than itself and one.  The only even integer is 2 because all other even integers are divisible by two.  This means 4, 6, 8, 10, 12, … are all composite because they are divisible by two.  The first ten prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

There are many lists of prime numbers at websites on the internet.  There are also lists of the largest prime numbers and top 20 largest prime numbers of certain forms like Mersenne, Fermat, Generalized Mersenne, Generalized Fermat, etc.  There are applets that can search for prime numbers on the computer.

There are many distributed computing programs going on continuously that are trying to find the largest prime number and the largest prime number of special forms.  The Gimps distributing project has found many large primes, including the current largest prime that is 12,978,189 digits.  They only search for primes of the Mersenne form (2^p-1).  The largest prime found to date was 2^43112609-1.  It is not known if primes of the Mersenne form are infinite.  It is known that for a Mersenne number to be prime, the exponent of two must also be a prime number.  But most Mersenne numbers are not prime even if the exponent is prime.  One interesting thing about Mersenne primes is every perfect number is formed by a Mersenne prime, as discovered by Euclid.  A perfect number is a number that adds up to its proper divisors.  For example, 6 is a perfect number because 6=1+2+3.  The product that always forms an even perfect number is (2^p-1)(2^(p-1)).  It is not known if there are any odd perfect numbers.

There are many theorems about prime numbers.  One of the most famous is Fermat’s Little Theorem, which states that (a^p-1)-1 is divisible by p only if p is prime.  The converse, unfortunately, is not true because p can be a composite number and the theorem can still hold.  These integers are called Carmichael numbers.  Wilson’s theorem is always true, but it deals with integers that are too hard to compute using computers.  Wilson’s Theorem states that an integer p is prime if and only if (p-1) factorial plus one is divisible by p.  A factorial is the product of integers up to and including that integer. For example,  four factorial is 1x2x3x4=24.

The story for finding Fermat primes is different. Just like the Mersenne form, it has not been proven that primes of this form are infinite.  The Fermat form is 2^n+1.  The largest Fermat prime found to date is only five digits.  It is 2^16+1=65,537. It is known that for a Fermat number to be prime, the exponent of two must be a power of 2 (2, 4, 8, 16, 32, 64, 128, 256, …).

A few years after the start of the distributing projects for Mersenne primes and Fermat primes, searches for the Generalized Mersenne primes and Generalized Fermat primes began.  The largest Generalized Fermat prime found to date is 145310^262144+1.  It has 1,353,265 digits.  It was found February, 2011.