Prime Numbers

We have seen that whole numbers which cannot be divided by any number, other than 1 and the number itself, are called Prime Numbers. For example, 7 is a prime as its factors are only 1 & 7. 6 is not prime since its factors are 1, 2, 3 & 6.

Definition of Primes

The current definition is that "a prime number is a positive integer greater than 1' that cannot be written as a product of two distinct integers which are greater than 1."

Greeks discovered that any whole number can be written as a product of powers of prime numbers "in an unique way". This is called the Fundamental Theorem of Arithmetic which we will see in detail in the next chapter. For this reason, prime Numbers are considered the building blocks of all numbers.

Sieve of Eratosthenes

Prime numbers have been studied right from early days of mathematics. Eratosthenes, a Greek mathematician who lived in the 3rd century BCE, evolved a systematic way of locating all prime numbers up to any desired number.

You start with a grid of numbers from 1 to the desired number. The user systematically crosses out numbers which can be divided by prime numbers starting with 2, 3, 5 and so on. Ultimately only the prime numbers would be left uncrossed.

For obvious reasons, it was called the Sieve of Eratosthenes.

A lot of higher mathematics is based on primes. There are many theorems in Number Theory which involve Prime numbers. We will now see a few interesting facts about them.

1 is not prime

The Fundamental Theorem of Arithmetic is one of the most important ideas. The primacy of of this theorem enforces the "rule" that both 1 & 2 cannot be considered to be prime numbers.

1 is a factor of every number and product of any number of 1s has the same value. So if 1 is taken as a prime, there cannot be an unique representation for any number as a product of primes. 6 can be written as 2 & 3 or 1, 2 & 3 or 1, 1, 2 & 3!. Hence mathematicians have decided that 1 will not be considered a prime.

2 is a prime as well as even

Every alternate whole number is an even number which has 2 as a factor. So for the sake of unique representation, 2 is considered as a prime number.

Also 2 obeys the basic condition for being a prime number. It has only 2 factors; 1 and itself which is 2!.

So 2 becomes the only even prime!

Goldbach"s Conjecture

In 1742, Christian Goldbach made the conjecture that "any even number can be written as the sum of 2 prime numbers". Even after analysing millions of numbers, no exception to this conjecture has been found.

At the same time, no one has been able to provide a proof as to the truth of this conjecture.

This is an example of a math idea which can be understood by a primary class student, whose proof is still eluding the best mathematical brains.

This is also an example of a proposition from Number Theory which we dealt with in the previous chapter.

Infinite number of primes

We know that whole numbers never end. There are infinite number of whole numbers. Is this true of prime numbers also?

Question like this reveal the abstract nature of math. And the fact that we can answer this question with logical thinking. This also shows the power of math.

Euclid gave a very elegant proof that there are an infinite number of primes. His proof showed that with the known primes, we can always construct another bigger prime.

Further, no detectable pattern has been seen in the sequence of primes. Finding a function which will predict how primes are distributed over the real number line is an intensely studied problem.

An Interesting Prime

If you write the numbers from 82 to 1 in descending order, you will get a 155-digit prime number.

8281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232212019181716151413121110987654321 is a prime!

The Need for Cryptography

During World War II, techniques for "coding" secret messages evolved. These techniques developed into the mathematical science of Cryptography.

One technique could be to change a word like "Money" into another word "Nlmvb" using a simple rule. Each letter has been replaced by its counterpart reading the alphabet in the reverse direction. "y" is the 25th letter (2nd from last) and it is replaced by "b"(2nd from the first).

The rule is is called the "key" to the coding. Unless some one knows the key, the original word cannot be deciphered.

Invention of computer software accelerated the development.

With the development of computers & telecommunications vast amounts of financial and confidential data started being sent through them. Such data could easily be accessed by persons who know the technical workings of a computer network. Hence the issue of safety of the data became critical. One solution was to "code" the data using various techniques so that only those who knew the code could read them.

With the spread of digital transfers of data there rose a need to encrypt the data for secrecy, in real time. Many sophisticated systems of encrypting were invented.

Use of Primes in Cryptography

Until 1970s prime numbers were mostly studied only as exercises in mathematical logic. Then their use in cryptography was discovered.

It used a simple fact that, when 2 very large primes are multiplied to get a product, it is almost impossible, even using computers, to find the two original primes from the product.

Two very large (with hundreds of digits) prime numbers was used to generate the keys required to decrypt the data. Their product was available. The safety of this method rests on the fact that factorizing the product of such huge prime numbers was almost impossible even using superfast computers.

Largest identified prime

The use of primes in cryptography motivated the discovery of larger and larger primes. But, even with a computer, the larger the number, more difficult the process to check if it is a prime.

Faster computers were used for this. Hence faster algorithms and computer programs were also developed to check if a number is prime.

About 30 years back mathematicians have started an ongoing project called (GIMPS) the Great Internet Mersenne Prime Search, basically to discover larger & larger primes.

A Mersenne prime is a prime number that can be written as 2p - 1, where p is also a prime number.

The largest known prime number discovered -

As of July 2018, is 277,232,917 − 1, a number with 23,249,425 digits.

As of October 2023, is 282,589,933 − 1, a number with 24,862,048 digits.

Primes in the Search for Intelligent Life in the Universe

Scientists have made a reasonable guess that if there are other intelligent beings in the Universe, they would have discovered the basics of mathematics and would be aware of prime numbers. Hence one idea of discovering any intelligent life is to send a message containing the sequence of primes in terms of simple dots & dashes.

The first such effort was made in 1967 when the Arecibo radio telescope in Puerto Rico was inaugurated. A message of length 1679 was sent to a star cluster about 25,000 light years away. It was a pictograph involving the use of primes, designed by Frank Drake of Cornell University. 1679 was a semi-prime which was the product of 2 primes 73 X23. No reply has been received until now.

Prime Numbers & Life Cycle of Cicadas

Cicadas are insects best known for the "piercing shrill" noises they create. Most of the more than 1500 species have annual breeding cycles.

There are a few which are known as "periodic" cicadas. These appear, mate, lay eggs & die in intervals of 7, 13 & 17.

If you notice, these 3 numbers are primes which have no common factors. So the chances of two of these species appearing together in any year is very low.

For example, a 13-year cycle and 17-year cycle will meet only every 221 years. That means that both species of cicadas would come out in huge numbers and all have to compete for the same amount of food only once every 221 years.

This possibly helps them to avoid competition for food and hence increase chances of propagating their species!

This is obviously an instance of a "mathematical structure" embedded in their brains which has been utilised by evolution in its fight for "survival of the fittest."

In late April of 2024, two broods of cicadas, one with a 13 year cycle & another with a 17 year cycle are expected to emerge together. The last time this happened was in 1803 which is 221 years back. 221 happens to be a common multiple of 13 & 17!