✖

Prime Numbers

Prime numbers are numbers that are divisible only by one and by themselves. The properties of prime numbers are often used, for example, in cryptography.

Definitions and examples

A prime number is a natural number that is divisible by one and itself without remainder, where one itself is not a prime number. The smallest prime number is two - it is divisible without remainder by one and two. It is also the only prime number that is even. All other primes are odd, because any other even number is divisible by two in addition to one and itself.

The sequence of several prime numbers: 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...

Prime numbers are related to the fundamental theorem of arithmetic, which states that any integer greater than 1 can be decomposed into a product of prime numbers.

Test whether a number is prime

Properties of prime numbers

  • There are infinitely many prime numbers. The proof can be found in the article on proof by contradiction.
  • For every integer z>1, there is at least one prime number in the interval (z, 2z). Example: for z = 2 we have the interval (2, 4). The only integer that is in this interval is three, and it is prime. For z = 5 we get the interval (5, 10), that is, the numbers 6, 7, 8, 9. The number 7 is a prime number. Similarly for the higher z.
  • A Mersenne prime is a prime number that is one less than some integer power of two. Thus the Mersenne prime M has the form M = 2z − 1, where z is an arbitrary natural number. An example would be the prime number 3, since 22 − 1 = 3 holds. Or 7, because 23 − 1 = 7.
  • The largest prime number known so far is thus the Mersenne prime, denoted M43112609, where the subscript determines the exponent z. It is thus the prime number 243112609−1. It was found on August 23, 2008 and has 12,978,189 digits.(Wikipedia)

Sequence without prime numbers

An arbitrarily long finite sequence of consecutive natural numbers can be found, among which there is no prime number. Such a sequence can be of the form k!+2, k!+3, …, k!+k and contains k − 1 consecutive composite numbers (the exclamation mark is a factorial).

For example, for k = 6 we get five consecutive composite numbers of the form: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. These numbers are successively divisible by two, three, four, five, and six, because the number 6! = 720 is definitely divisible by all of these numbers, since it was formed by their product: 6! = 6 · 5 · 4 · 3 · 2. If the number 720 is divisible by three, then the number 720 + 3 must also be divisible by three. Similarly for the others.

The Little Fermat Theorem

For every prime p and for every integer z such that z is not a multiple of p, the number zp − z is divisible by the prime p.

Example: consider the prime number p = 3 and the integer z = 4. The number four is not a multiple of three, so we can continue. Let's calculate the value of 43 − 4. This is equal to 60. But in doing so, 60/4 = 15, the number four thus divides sixty without remainder, which is equivalent to Fermat's theorem. Another example: p = 7, z = 10. We calculate the intermediate result 107 − 10 = 9999990 and divide this number by seven: 9999990/7 = 1428570. Again, we get the result without remainder.

Unsolved questions

There are many well-known hypotheses concerning prime numbers that have not yet (2011) been proved or disproved. Two of the best known are:

  • Infinity of prime pairs: a prime pair is a pair of numbers (z, z + 2), both of which are prime numbers. For example, (3, 5) or (29, 31). The question is whether these prime pairs are infinitely many. It is assumed that they are, but the proof is lacking.(Wikipedia)
  • Riemann Hypothesis: All non-trivial zero points of the Riemann zeta function have a real part equal to $\frac12$.(Wikipedia) The theorem is related to the distribution of prime numbers and is one of the so-called Millennium Problems, and there is a million dollar reward for solving it.