Prime Numbers: An Introduction

Prime number is the number, which is greater than 1 and cannot be divided by any number excluding itself and one. A prime number is a positive integer that has just two positive integer factors, including 1 and itself. Such as, if the factors of 28 are listed, there are 6 factors that are 1, 2, 4, 7, 14, and 28. Similarly, if the factors of 29 are listed, there are only two factors that are 1 and 29. Therefore, it can be inferred that 29 is a prime number, but 28 is not.

Examples of prime numbers

The first few prime numbers are as follows:

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, etc.

Identifying the primes

The ancient Sieve of Eratosthenes is a simple way to work out all prime numbers up to a given limit by preparing a list of all integers and repetitively striking out multiples of already found primes. There is also a modern Sieve of Atkin, which is more complex when compared to that of Eratosthenes.

A method to determine whether a number is prime or not, is to divide it by all primes less than or equal to the square root of that number. If the results of any of the divisions are an integer, the original number is not a prime and if not, it is a prime. One need not actually calculate the square root; once one sees that the quotient is less than the divisor, one can stop. This is called as the trial division, which is the simplest primality test but it is impractical for testing large integers because the number of possible factors grows exponentially as the number of digits in the number to be tested increases.

Primality tests: A primality test algorithm is an algorithm that is used to test a number for primality, that is, whether the number is a prime number or not.

• AKS primality test

The AKS primality test is based upon the equivalence

(x – a)ⁿ = (xⁿ – a) (mod n) for a coprime to n, which is true if and only if n is prime. This is a generalization of Fermat’s little theorem extended to polynomials and can easily be proven using the binomial theorem together with the fact that: for all 0 < k < n if n is prime. While this equivalence constitutes a primality test in itself, verifying it takes exponential time. Therefore AKS makes use of a related equivalence

(x – a)ⁿ = (xⁿ – a) (mod n, x ^r – 1), which can be checked in polynomial time.

• Fermat primality test

Fermat’s little theorem asserts that if p is prime and 1≤ a < p, then

a ^{p -1}≡ 1 (mod p)

In order to test whether p is a prime number or not, one can pick random a’s in the interval and check if there is an equality.

• Solovay-Strassen primality test

For a prime number p and any integer a,

A ^{(p -1)/2} ≡ (a/p) (mod p)

Where (a/p) is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to (a/n); where n can be any odd integer. The Jacobi symbol can be computed in time O((log n)²) using Jacobi’s generalization of law of quadratic reciprocity.

It can be observed whether or not the congruence

A ^{(n -1)/2} ≡ (a/n) (mod n) holds for various values of a. This congruence is true for all a’s if n is a prime number. (Solovay, Robert M. and Volker Strassen, 1977)

• Lucas-Lehmer test

This test is for a natural number n and in this test, it is also required that the prime factors of n − 1 should be already known.

If for every prime factor (q) of n − 1, there exists an integer a less than n and greater than 1 such as

a ^{n -1} ≡1 (mod n)

and then

a ^{n -1/q} 1 (mod n)

then n is prime. If no such number can be found, n is composite number.

• Miller-Rabin primality test

If we can find an a such that

a^d ≡ 1 (mod n), and

a^2nd -1 (mod n) for all 0 ≤ r ≤ s – 1

then ‘a’ proves the compositeness of n. If not, ‘a’ is called a strong liar, and n is a strong probable prime to the base a. “Strong liar” refers to the case where n is composite but yet the equations hold as they would for a prime number.

There are several witnesses ‘a’ for every odd composite n. But, a simple way to generate such an ‘a’ is known. Making the test probabilistic is the solution: we choose randomly, and check whether it is a witness for the composite nature of n. If n is composite, majority of the ‘a’s are witnesses, therefore the test will discover n as a composite number with high probability. (Rabin, 1980)

A probable prime is an integer, which is considered to be probably prime by passing a certain test. Probable primes, which are actually composite (such as Carmichael numbers) are known as pseudoprimes.

Besides these methods, there are other methods also. There is a set of Diophantine equations in 9 variables and one parameter in which the parameter is a prime number only if the resultant system of equations has a solution over the natural numbers. A single formula with the property of all the positive values being prime can be obtained with this method. There is another formula that is based on Wilson’s theorem. The number ‘two’ is generated several times and all other primes are generated exactly once. Also, there are other similar formulas that can generate primes. Some primes are categorized as per the properties of their digits in decimal or other bases. An example is that the numbers whose digits develop a palindromic sequence are palindromic primes, and if by consecutively removing the first digit at the left or the right generates only new prime numbers, a prime number is known as a truncatable prime.

The first 5,000 prime numbers can be known very quickly by just looking at odd numbers and checking each new number (say 5) against every number above it (3); so if 5Mod3 = 0 then it’s not a prime number.

History of prime numbers

The most ancient and acknowledged proof for the statement that “There are infinitely many prime numbers”, is given by Euclid in his Elements (Book IX, Proposition 20). The Sieve of Eratosthenes is a simple, ancient algorithm to identify all prime numbers up to a particular integer. After this, came the modern Sieve of Atkin, which is faster but more complex. The Sieve of Eratosthenes was created in the 3rd century BC by Eratosthenes. Some clues can be found in the surviving records of the ancient Egyptians regarding their knowledge of prime numbers: for example, the Egyptian fraction expansions in the Rhind papyrus have fairly different forms for primes and for composites. But, the first surviving records of the clear study of prime numbers come from the Ancient Greeks. Euclid’s Elements (circa 300 BC) include key theorems about primes, counting the fundamental theorem of arithmetic and the infinitude of primes. Euclid also explained how a perfect number is constructed from a Mersenne prime.

After the Greeks, nothing special happened with the study of prime numbers till the 17th century. In 1640, Pierre de Fermat affirmed Fermat’s little theorem, which was later on proved by Leibniz and Euler. Chinese may have identified a special case of Fermat’s theorem much earlier. Fermat assumed that all numbers of the form 22n + 1 are prime and he proved this up to n = 4. But, the subsequent Fermat number 232+1 is composite; whose one prime factor is 641). This was later on discovered by Euler and now no further Fermat numbers are recognized as prime numbers. A French monk, Marin Mersenne looked at primes of the form 2p – 1, with p as a prime number. They are known as Mersenne primes after his name.

Euler showed that the infinite series 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … is divergent. In 1747, Euler demonstrated that even the perfect numbers are in particular the integers of the form 2p-1(2p-1), where the second factor is a Mersenne prime. It is supposed that there are no odd perfect numbers, but it is not proved yet. In the beginning of the 19th century, Legendre and Gauss independently assumed that because x tends to infinity, the number of primes up to x is asymptotic to x/log(x), where log(x) is the natural logarithm of x.

Awards for finding primes

A prize of US$100,000 has been offered by the Electronic Frontier Foundation (EFF) to the first discoverers of a prime with a minimum 10 million digits. Also, $150,000 for 100 million digits, and $250,000 for 1 billion digits has been offered. In 2000, $50,000 for 1 million digits were paid. Apart from this, prizes up to US$200,000 for finding the prime factors of particular semi-primes of up to 2048 bits were offered by the RSA Factoring Challenge.

Facts about prime numbers

• 73939133 is an amazing prime number. If the last or the digit at the units place is removed, every time you will get a prime number. It is the largest known prime with this property. Because, all the numbers which we get after removing the end digit of the number are also prime numbers. They are as follows: 7393913, 739391, 73939, 7393, 739, 73 and 7. All these numbers are prime numbers. This is a distinct quality of the number 73939133, which any other number does not have. (Amazing number facts, 2008)

• The only even prime number is 2. All other even numbers can be divided by 2. So, they are not prime numbers.

• Zero and 1 are not considered to be prime numbers.

• If the sum of the digits of a number is a multiple of 3, that number can be divided by 3.

• With the exception of 0 and 1, a number is either a prime number or a composite number. A composite number is identified as any number that is greater than 1 and that is not prime.

• The last digit of a prime number greater than 5 can never be 5. Any number greater than 5 whose last digit is 5 can be divided by 5. (Prime Numbers, 2008)

For some of the prime numbers, the size of the repeating block is 1 less than the prime.

These are known as Golden 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

9 primes out of the 25 (less than 100) are golden primes; this forms 36% (9/25). (Amazing number facts, 2008)

Examples of mathematicians specialized in prime numbers

Arthur Wieferich, D. D. Wall, Zhi Hong Sun and Zhi Wei Sun, Joseph Wolstenholme, Joseph Wolstenholme, Euclid, Eratosthenes.

Applications of prime numbers

For a long time, the number theory and the study of prime numbers as well was seen as the canonical example of pure mathematics with no applications beyond the self-interest of studying the topic. But, in the 1970s, it was publicly announced that prime numbers could be used as a basis for creating the public key cryptography algorithms. They were also used for hash tables and pseudorandom number generators.

A number of rotor machines were designed with a different number of pins on each rotor. The number of pins on any one rotor was either prime, or co-prime to the number of pins on any other rotor. With this, a full cycle of possible rotor positions (before repeating any position) was generated.

Prime numbers in the arts and literature

Also, prime numbers have had a significant influence on several artists and writers. The French composer Olivier Messiaen created ametrical music through “natural phenomena” with the use of prime numbers. In his works, La Nativité du Seigneur (1935) and Quatre études de rythme (1949-50), he has used motifs with lengths given by different prime numbers to create unpredictable rhythms: 41, 43, 47 and 53 are the primes that appear in one of the études. A scientist of NASA, Carl Sagan recommended (in his science fiction ‘Contact’) that prime numbers could be used for communication with the aliens. The award-winning play ‘Arcadia’ by Tom Stoppard was a willful attempt made to discuss mathematical ideas on the stage. In the very first scene, the 13 year old heroine baffles over the Fermat’s last theorem (theorem that involves prime numbers). A popular fascination with the mysteries of prime numbers and cryptography has been seen in various films.

References

Amazing number facts, 2008. Retrieved April 28, 2008 from http://www.madras.fife.sch.uk/maths/amazingnofacts/fact018.html

Prime Numbers, 2008. Retrieved April 28, 2008 from http://www.factmonster.com/ipka/A0876084.html

Solovay, Robert M. & Strassen, V. (1977). “A fast Monte-Carlo test for primality”. SIAM Journal on Computing 6 (1): 84-85.

Rabin, M.O. (1980). Probabilistic algorithm for testing primality, Journal of Number Theory 12, no. 1, pp. 128-138.