Home > Number theory

# Prime numbers

Prime numbers are simple but crucial to number theory. A prime number is simply a number that is not divisible by any number except 1 or itself. For example, 35 is divisible by 5 and 7 so 35 is not prime. However, 7 is prime. Any number that is not prime is composite. The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Note that 1 is not prime for technical reasons. Also, all composite numbers can uniquely be expressed by multiplying prime numbers.This is its prime factorisation. Ignoring order, there is only one possible way to do this. This is the fundamental theorem of arithmetic and is crucial to mathematics.

One easy way to tell whether a number is prime is to try dividing it by all numbers up to its square root. If there are no divisors up to its square root, it is prime. However, for primes with hundreds of digits, this is incredibly slow and cumbersome. Faster methods exist. Some methods are especially fast for certain types of primes. However, there are an infinite number of primes. A proof was shown by Euclid. Suppose you have a finite list of primes. Multiply them all together. This new number is divisible by all primes. Now add 1 to get a number not divisible by any primes in our list. Thus it is either composite and has a prime factor not on our list or is prime and is not on our list. Either way, there is a prime number not on our list.

There are many types of prime numbers. Twin primes are primes that are in a pair. A pair of twin primes must have a difference of 2. For example, 41 and 43 are twin primes. Twin primes are much rarer than other primes. In fact, we do not know if there are infinitely many of them. The twin primes conjecture states that there are infinitely many twin primes.

Other types of primes exist. There are the Mersenne primes, which are 2p-1 for some prime p. The largest prime discovered is usually a Mersenne prime. It is currently 257885161-1 with 17425170 digits. It is conjectured that there are infinitely many Mersenne primes.

There are many more conjectures. Goldbach's conjecture states that every even number greater than 2 is the sum of two prime numbers. No one has proved this yet and it seems incredibly difficult to prove. We do know that all even numbers are either the sum of two primes or the sum of a prime and the product of two other primes. Also, there is the Euclid-Mullin conjecture. First create a list starting with 2. The next term is the least prime factor of one more than the product of all terms so far. The list goes: 2, 3, 7, 43, 13, 53, 5, 6221671... The conjecture posed by Mullin in 1963 was whether all primes appear in this list. It is also named after Euclid as the list is constructed using his method to prove that there are infinitely many primes.

## Related entries

•Prime Problems