Euclid, algorithm and the infinitude of primes

Every mathphile knows about Euclid of Alexandria who was a famous Greek mathematician who is said to have been active around 300 BC i.e. 2300 yrs ago. Euclid is popularly held as the founder of geometry. His set of books called 'elements' contained theorems and proofs on what is known as 'Euclidean geometry' which majority of school going students read and solve from their school textbooks these days. Much has been written on Euclid's contribution to geometry. Let me share a few of his mind-boggling works in number theory later in this post.

Much of the works in number theory when Greek math was at its peak revolved around identifying different types of numbers such as odd, even, prime, composite numbers, polygonal numbers, perfect numbers etc and creating algorithms to find such numbers. The famous 'Sieve of Eratosthenes' is an algorithm to find and identify prime numbers.

Now let me first introduce the word 'algorithm'. The etymology of the word 'algorithm' is an interesting one. The name comes from the famous Islamic mathematician 'Al Khwarizmi' populary known as founder of algebra. He wrote a book on Hindu Arabic numeral system and thus paved the way for commercialisation and usage of the same in medieval Europe. Interestingly the works of Al Khwarizmi were heavily borrowed from the works of Indian mathematicians like Brahmagupta.

Now we as a layman know that algorithm means a systemic way of computing. For instance when we read series( finite and infinite) and progressions we find the general way of representing the nth term of the series and thus are able to calculate sum of the terms using mathematical techniques like in case of AP, GP, AGP, binomials, multinomials etc.

So algorithm basically arrives with a system of introducing variables thereby helping to create a general pattern as we see in fibonacci or any other series. Interestingly the world's initial algorithms were related to computing of roots of the polynomial equation and identifying pythagorean triplets. Greeks even used to write these set of pythagorean triplets on what we call 'plimptons'. The world these days say that Coding( algorithmic thinking and understanding of systems) will become the third major subject after math (numerical ability and english (reading and comprehension skills). I don' know much about future as we are in extremistan as NN Taleb puts wherein innovation and disruption is the norm. But have we changed much inside? I don't think so. Maslow' pyramid remains the same. Now let me take you to Euclid's algorithm.

The simplest division algorithm, historically incorporated into a greatest common divisor algorithm presented in Euclid's Elements, Book VII, Proposition 1, finds the remainder given two positive integers using only subtractions and comparisons:

while N ≥ D do

N := N − D

end

return N

Greeks and mathematicians in general always have fascination for prime numbers. The interest lied right from identifying them to know the exact number of them and finally the distribution of the primes. Euclid also proved that infinite number of prime numbers are possible. Here is the proof-:

Given any finite collection of primes p1, p2, . . . , pn, we can find another

by considering

p = p1 p2 · · · pn + 1.

This number is not divisible by p1, p2, . . . , pn (each leaves remainder 1).

Hence either p itself is a prime, and p > p1, p2, . . . , pn, or else it has a

prime divisor other than p1, p2, . . . , pn.

We can thus see an algorithmic mind has always been intuitive to human beings who have always found ways to platonize the randomness of nature and tried to overcome adversity by observing patterns, bulding machines, equipments and modern tech etc. Euclid, Archimedes, Galileo, Newton, Euler, Descartes, CF Gauss, Riemann, Einstein and innovators like Watt, Wright brothers, Tesla, Edison and recently NASA, Apple, Space X and Tesla Inc have been the pioneers of this scientific journey. The journey of algorithms and scientific progress has been fascinating. From just solving puzzles to building machines and now even playing even with genes and finding potential cure for diseases like Alzheimer, AIDS and cancer is possible courtesy our algorithmic thinking and CRISPR and AI like technology.