The Magic of Prime Numbers
As R. Courant and H. Robbins say in his famous book "What is mathematics", most statements in mathematics are concerned not with a single object – like a concrete number, but with a class of objects, like all even integers,
2, 4, 6, 8,... or
the class of all integers divisible by 3,
In number theory, of a fundamental interest is a class of all primes or prime numbers. While numbers like 10, 12 or 15 can be represented as a product of smaller factors,
prime numbers cannot be resolved in that way.
More precisely, prime number is an integer, greater than 1, which is divisible only by itself and one. Thus, in the set of natural numbers prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,...
One of the first questions related to prime numbers is whether there is finitely of infinitely many such numbers. The answer is found by a Greek mathematician Euclid: there is infinitely many primes in the set of natural numbers. Although, in general, proofs of the mentioned facts are out of the scope of this articles, we will give this proof since it is rather simple and a very nice example of a proof by contradiction.
There are two distinct types of natural numbers:
- prime numbers
- composite numbers.
The number one is neither prime nor composite.
Firstly, we conclude that there are only two possibilities: the number of primes is either finite or infinite. Now suppose that the number of primes is finite and all prime numbers are p1,p2,...,pn. Let construct the number A
Obviously, A is grater than any prime p but it is not divisible by any of p. In case the assumption is true, than A should be divisible by at least one of the primes. However, the remainder is always 1. So, since we have only two possibilities here and one of them leads to a contradiction, we conclude that alternative statement is the right one.
Primes – building blocks of integers
Prime numbers can be understood as building blocks of the set of all integers. For example,
Every composite number (i.e. the number which is not prime) can be represented as a product of primes. Moreover, one remarkable property holds for this factorization – it is unique! Every integer (greater than 1) can be factored into a product of primes in only one way. The rule is known as the fundamental theorem of arithmetic.
Ulam spiral - graphical presentation of primes in the plane
Searching for a prime formula
The Eratosthenes sieve (see the video below) is a procedure of listing all the primes up to any given integer N. Firstly we strike out all those numbers up to N which are multiples of 2, then all those remaining which are multiples of 3 and so on until all composite numbers have been striking out.
However, mathematicians were looking for more elegant way of generating the primes, they are seeking for a formula producing all the primes. A famous French mathematician Pierre de Fermat (1601-1665) made the conjecture that all the numbers of the form
are prime numbers. One can easily check that this is true for n=1,2,3,4:
However, the conjectures is not true since yet for F(5) we have a composite number. Namely, in 1732 a Swiss mathematician and physicist L. Euler (1707-1783) discovered that F(5)=641*6700417, thus F(5) is not prime.
Prime numbers of the above form are called Fermat primes. Although Fermat formula was false for the purpose to produce all primes, there is a remarkable relation between the Fermat primes and the existence of a construction of a regular plane polygon with ruler and compasses only. As it is proved by a German mathematician C. F. Gauss, regular plane polygon with p sides, where p is a prime, is capable of such a construction if and only if p is a Fermat prime. (So, it holds both: if such a construction is possible then p is a Fermat prime, and if p is a Fermat prime than construction is possible.)
Unsolved question at present is whether there are finitely or infinitely many Fermat primes.
Mersenne number is a number of the form Mn=2n-1, which means that Mersenne numbers consist of all 1s in base 2.
When the number of the form 2n-1 is prime it is called Mersenne prime, after a French scientist M. Mersenne (1588-1648). Namely, Mersenne conjectured that the numbers 2n-1 were primes for n=2, 3, 5, 7, 13, 17,19,31,67,127 and 257. Letter it was shown that the correct list is 2,3,5,7,13,17,19,31,61,89,107 and 127. It is known that if 2p-1 is prime then p is prime. Mersenne primes are of particular interest in providing examples of large prime numbers. For example,
244497- 1 is the 27th Mersenne prime,
243112609 -1 is currently the largest known prime number.
Density of primes
Finally, mathematicians turned to investigation of the distribution of primes among the natural numbers instead of looking for an exact formula for primes. Let Pn be the number of primes among the integers 1,2,...,n. Instead of looking for an equation resulting with Pn for a given n, we are going to deal with the ratio Pn/n, which can be understand as a "density" of primes. It can be shown that this ratio decline with n logarithmically. More precisely,
lim Pn/n =1/ln (n) when n goes to infinity.
This result, describing the distribution of primes, is known as the prime number theorem.
There are also other nice rules prescribing the presence of primes in the whole set of natural numbers. One remarkable fact showing that primes are "well distributed" is that for every n>1, there is always a prime between n and 2n (Bertrand's postulate).
After many effort of a few scientists, a German mathematician L. Dirichlet (1805-1859) finally succeeded to prove that in an arithmetical progression there are infinitely many primes. More precisely in any progression a, a+d, a+2d,...,a+nd, where a and d have no common factor, there are infinitely many prime members of the progression.
Twin primes conjecture
There are a few remarkable properties of primes observed that are neither proved nor disproved. Twin prime conjecture says that there are infinitely many "twin" primes i.e. infinitely many pairs of primes with the difference 2. Such pairs are
3 and 5,
11 and 13,
17 and 19, etc.
Interestingly, an analogy with twin prime conjecture is proven in the case of Apollonian circle package. Starting with the three mutually tangent circles there are two other circles touching all of them, one of two is the outer circle. Furthermore, we can continue to fill the gap between any three circles, with a new circle. Let assume that the first three circles have rational radius. In such a set of circles there are infinitely many mutually tangent pairs of circles with prime curvature (curvature is reciprocally of radius).
A German mathematician C. Goldbach (1690-1764) in his letter to Euler conjectured that every even number can be represented as the sum of two primes (except 2, which is itself a prime). For example:
First breakthrough towards the possible proof was done by a Russian mathematician L. Schnirelmann in 1931, who proved that every positive integer can be represented as the sum of not more than 300000 primes. Later a Russian mathematician A. I. Vinogradov and an Indian mathematician S. Ramanujan reduced the number from 300000 to 4. However, it doesn't hold for the all integers but for all integers greater than a certain integer N. Goldbach conjecture still remains one of the oldest and the most famous open problems in number theory and in the whole mathematics.
A primality test is a procedure that determines whether a given number is prime or not. One simple method would be to check if a given number N is divisible by any number between 3 and square root of N. If there is at least one number in this range that divide N than N is composite, otherwise it is not.
Some known theorems as the Fermat's Little Theorem and Wilson's Theorem can serve as the test or as a base for some more sophisticated and more efficient tests. Wilson's theorem states that a number p is prime if and only if
(p-1)! ≡ -1 (mod p)
For example if p=5 than we have (5-1)!=1*2*3*4=24, 24 mod 5 ≡ 4 ≡ -1. Thus, 5 is a prime, whereas p=6 is not: (6-1)!=120, 120 mod 6 ≡ 0.
The disadvantage of the method is that it needs many multiplication in case of bigger numbers.
A search for largest known prime has always intrigued not only mathematicians but the broader community as well. There is even an award granted by a non-profit organization Electronic Frontier Foundation for the largest prime found. Currently the largest known prime is a Mersenne number with the exponent 43112609 with 12978189 digits, found in 2008.
The Sieve of Eratosthenes
- Natural numbers can be either prime or composite.
- Every natural number can be represented as a product of primes and this factorization is unique.
- There are infinitely many primes in the set of all natural numbers.
- The "density" of primes decline logarithmically; there is always a prime between numbers n and 2n.
- Two the most famous open question regarding primes are twin prime conjecture and Goldbach conjecture.
- Regular polygon with p sides, p being prime, is constructable by rule and compass only if and only if p is a Fermat prime.
- Wilson's theorem can serve as a primality test but direct usage is impractical for bigger numbers.
A short quiz...
view quiz statistics
This chartlets is an excellent help for learning. It measure 17'' x 22'' and includes a resource guide.
An amazing book on prime numbers. Very clear and nicely explained everything about primes. Available in hardcover and kindle edition.