Prime numbers
Prime numbers are numbers divisible only by 1 and by themselves. The properties of primes are widely used, for example, in cryptography.
Definition and examples
A prime number is a positive integer that is divisible without remainder only by 1 and by itself, and 1 itself is not a prime. The smallest prime is 2 – it is divisible without remainder by 1 and 2. It is also the only prime that is even. All other primes are odd, because any other even number is divisible by 2 as well as by 1 and itself.
The first few primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271…
Primes are linked to the fundamental theorem of arithmetic, which says that every integer greater than 1 can be written as a product of primes.
Test whether a number is prime
Properties of primes
- There are infinitely many primes. You can find the proof in the article on proof by contradiction.
- For every integer z>1 there is at least one prime in the interval (z, 2z). Example: for z = 2 we get the interval (2, 4). The only integer in this interval is 3, and that is a prime. For z = 5 we get the interval (5, 10), that is, the numbers 6, 7, 8, 9. The number 7 is a prime. The same goes for larger z.
- A Mersenne prime is a prime that is one less than some integer power of 2. So a Mersenne prime M has the form M = 2z − 1, where z is some positive integer. For example, 3 is a Mersenne prime because 22 − 1 = 3, and so is 7, because 23 − 1 = 7.
- The largest known primes tend to be Mersenne primes. For example, on 23 August 2008 the Mersenne prime M43112609 was found, where the subscript gives the exponent z. This is the prime 243112609 − 1, which has 12,978,189 digits and at the time was the largest known prime.
A sequence without primes
We can find a finite sequence of consecutive positive integers of any length that contains no primes at all. Such a sequence can have the form k!+2, k!+3, …, k!+k, and it contains k − 1 consecutive composite numbers (the exclamation mark is the factorial).
For example, for k = 6 we get five consecutive composite numbers: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. These are divisible by 2, 3, 4, 5 and 6 respectively, because 6! = 720 is certainly divisible by all of them, since it is their product: 6! = 6 · 5 · 4 · 3 · 2. If 720 is divisible by 3, then 720 + 3 must be divisible by 3 as well. The same goes for the others.
Fermat’s little theorem
For every prime p and every integer z, the number zp − z is divisible by p.
Example: take the prime p = 3 and the integer z = 4. We work out 43 − 4, which equals 60. And indeed 60/3 = 20, so three divides sixty without remainder, in line with Fermat’s theorem. Another example: p = 7, z = 10. We work out the intermediate result 107 − 10 = 9999990 and divide it by seven: 9999990/7 = 1428570. Again there is no remainder.
Unsolved questions
Many well-known conjectures about primes have not yet (as of 2011) been proved or disproved. Two of the best known are:
- Infinitely many twin primes: twin primes are a pair of numbers (z, z + 2) that are both prime. For example (3, 5) or (29, 31). The question is whether there are infinitely many such pairs. It is believed that there are, but nobody has a proof.
- The Riemann hypothesis: all non-trivial zeros of the Riemann zeta function have real part equal to
