Transcriber: Jeremy Ng Reviewer: Emma Gon
What were you doing at the age of 15?
Were you preparing for do or die competitive examinations?
Did you dream of changing the world?
Or were you simply trying to make sense of the world?
Were you practicing your favorite musical instrument or sport?
Or were you staring at a large table of prime numbers,
up to 3 million searching for patterns among them?
A prime number, as we learned in school,
is a natural number greater than one which has only two divisors:
one and itself, as such, a prime number cannot be written
as a product of smaller factors.
Prime numbers are the building blocks of all numbers.
Any number and greater than one is either a prime,
or it can be written as a product of prime numbers,
and it can be written uniquely as a product of prime numbers.
For example, 69 can be written as three times 23,
where both three and 23 are prime numbers.
No other primes can combine to give us 69.
Similarly, 27 can be written as three times, three times three,
and no other prime powers, all product of other primes, can give us 27.
This amazing fact is called the fundamental theorem of arithmetic.
Another amazing fact about prime numbers
is that there are infinitely many of them.
In a sense, this tells us
that primes are the building blocks of numbers
and that there are infinitely many types of building blocks to choose from.
This begs the question how do we gather these building blocks?
This question has multiple aspects.
First, if a very large number is placed before us,
do we know of a reasonable method to determine whether it is a prime or not?
Second, if a large table of numbers is arranged and placed in front of us,
do we know of a method by which we can establish
the primes in that table in one go?
In the year 240 BCE,
Eratosthenes, a Greek polymath, answered this question.
His fundamental observation was
that you can use small primes to identify larger primes.
His idea was that if you want to generate all the primes
up to some number N, you first identify prime numbers
up to square root of N.
Once you do that, take those small primes
and for each of them consider all possible multiples of those primes
and cross them out from your table.
What remains behind after this crossing out procedure has been carried out,
are all the prime numbers up to capital N.
For example, if you want to identify all the prime numbers up to 100,
first identify primes up to ten.
This is easy, these are 2, 3, 5 and 7.
Now, one by one, stop crossing out
the multiples of 2, 3, 5 and 7.
And whatever remains behind after you cross out
all these multiples are, in fact, all the primes up to 100.
Now, you can use all these primes up 100
to identify all the primes up to 10,000,
which is the square of a 100, in the same manner.
So the method of Eratosthenes is called a sieve,
and it gives us a new way of looking at prime numbers.
Prime numbers are those numbers
which are not fine enough to escape through the sieve of Eratosthenes.
A natural question, therefore, is
if we can find better sieves which can identify primes more efficiently.
This perspective led to a search for large prime tables,
especially in the 17th and 18th centuries
in England and in Germany.
And thus it was that in 1792,
a young 15 year old German teenager
by the name of Johann Carl Friedrich Gauss
found himself staring at a table of prime numbers
up to 3 million and wondered
if there were any patterns among those prime numbers.
He made a fundamental conjecture by analysing the data in batches.
So his conjecture was that if you take a large number x
and let it become larger and larger,
then the number of primes up to x, which is called pi of x,
is asymptotic to x over log x.
Now in the table that you'll see, you'll see values of x,
which are much higher than 3 million.
But you will notice that the ratio pi of x over x log x hovers around one,
and as x becomes larger and larger,
the ratio comes closer and closer to one.
So this provides some numerical evidence
for Gauss’s conjecture, but not a conclusive proof.
The conjecture of Gauss fascinated several scholars.
Now, this conjecture was proved more than 100 years later.
And we wonder at this point,
sometimes when we spend very long and work very hard to solve
a mathematical problem and yet can’t quite get there,
the limitation is not in our efforts.
Rather, the limitation could be among the tools and techniques
that are available to us at that point of time to solve that problem.
So the only way forward then
is to have a new idea, a fresh insight,
which can help us to view the problem in a different light.
This fresh insight was provided by another German mathematician,
Bernhard Riemann, in 1859
who interpreted the conjecture of Gauss
from the viewpoint of what are called the Riemann Zeta functions,
which he defined over the set of complex numbers.
Therefore a problem in arithmetic
got converted into a problem in complex analysis.
And this was the perspective
that finally led to a complete proof of the conjecture of Gauss.
This conjecture is now called the Prime Number Theorem.
Now, while looking at the Riemann Zeta functions,
Riemann also made some fundamental conjectures about these data functions.
One such conjecture is the Riemann hypothesis.
It is too technical to be described in this talk,
but you will be fascinated to know that 162 years down the line,
we still do not have a resolution of the Riemann hypothesis.
In fact, it is one of the Millennium Prize problems
announced by the Clay Maths Institute.
And if you were to resolve the Riemann hypothesis,
you will win a million dollars.
As I said, we are still far away from a resolution.
But we are now convinced that there are far easier ways
of earning a million dollars.
At this point, we wonder,
is mathematics all about somebody asking a question
and another person answering it more than a century later?
In a certain sense, yes, it is.
But the spirit behind asking a good question
is to push beyond existing boundaries.
A good question and a new idea
that arises in response to that question,
help us to reinterpret what we thought we understood well.
Sometimes multiple perspectives around a notion such as prime numbers
grow independently and develop lives of their own
and also come together to change our world.
In the year 1640 in France,
a young French lawyer by the name of Pierre de Fermat,
who spent his spare time doing mathematics,
made some pertinent observations about prime numbers.
He made this observation in a letter to a friend without proof.
This is his observation - if p is a prime number, then B divides
sorry...
If p is a prime number and A is any natural number
which is not divisible by p, then A raises to the p minus one
further subtracted by one must be divisible by p.
This fact is famously known as Fermat’s Little Theorem,
even though it was proved by Leonard Euler almost a century later.
Fermat’s Little Theorem helps us to view primes in a very different light.
And if you think about it carefully,
it also gives you a new way of determining
whether something is a prime or not.
Fermat’s Little Theorem,
as well as further investigations into prime numbers,
teach us three computational principles.
First, it is reasonably easy to generate a large prime.
Second, it is reasonably easy to determine
if that potential prime is indeed a prime.
And third, and this is extremely important,
it is very difficult to break down a large number and into its prime factors.
By easy, I mean that a job can be accomplished
in a reasonable amount of time using our computational tools.
And by difficult, I mean the exact opposite.
Even with all the computational resources available to us,
a difficult task can take several years to be accomplished.
Perhaps thousands and thousands of years.
Fermat’s Little Theorem,
along with these three computational principles,
can combine to give very beautiful applications
in cryptography and e-commerce.
In particular today, I would like to tell you
about three important applications of Fermat’s Little Theorem
without going into too much detail.
First is the Odyssey Public Key Crypto system
developed in the year 1978 by Rivest, Shamir and Edelman,
three computer scientists at MIT.
Today, the Odyssey Public Key Crypto System is used
in almost all digital transactions that we do,
especially online purchases and payments that we now do
on a daily basis, especially in India.
Next is the Miller-Rabin primality test,
which tells you how likely is a large number to be prime.
Now the Miller-Rabin test is an extremely important test.
It has found several applications in e-commerce and cryptography.
And we note here that if you are allowed to assume
a slight generalization of the Riemann hypothesis,
then the running time of this method can be cut down drastically.
Therefore, this test, the Miller-Rabin test
can go back to the ideas of Fermat as well as Riemann,
and which can be combined to give a very nice application.
The third application I want to tell you about today
is the Agrawal-Kayal Saxena primality test,
which was announced in the year 2002,
again by three computer scientists at IIT Kanpur.
Now this is the first deterministic polynomial time algorithm,
which does not make any assumptions, meaning it is unconditional.
And this algorithm determines whether a large number is prime or not.
It gives a definite answer, okay?
It gives a definite answer,
it gives the answer to you in a reasonable amount of time
and it does not make any unknown assumptions,
such as the Riemann hypothesis, it is an unconditional test.
The audience here would be fascinated to know
that the AKS primality test,
in fact grew out of an undergraduate research project
which was undertaken by Neeraj Kayal and Nitin Saxena
under the supervision of Professor Manindra Agrawal at IIT Kanpur.
Thus, a deep and interesting mathematical problem was solved
as part of a bachelor's project and today it is counted among
the most significant mathematical discoveries of the 21st century.
Something to reflect upon.
What do prime numbers teach us about the growth of ideas?
First, ideas grew through sheer joy in pursuing what we love.
When Fermat, a lawyer by profession, sat down to study prime numbers,
he was purely motivated by the joy of learning,
by the joy that the study brought to him.
Gauss is today called the Prince of Mathematics
due to his phenomenal and wide ranging contributions.
He loved numbers, as a young 15 year old,
he stared at a table of prime numbers up to 3 million
and Gauss made interesting guesses about patterns among those primes.
So prime numbers teach us that we should pursue joyfully,
honestly and unapologetically whatever we find beautiful and interesting.
Second, the seed of an idea can grow into a huge tree of knowledge
which can nourish and provide shade to many.
The branches of an idea as in the case of a grand banyan tree,
often grow into sturdy trees of their own.
When Fermat, Gauss, Riemann and many others
planted the seeds of their ideas and knowledge,
perhaps they did not anticipate the effect,
the impact that ideas will have on the world in the coming centuries.
Several centuries down the line,
their work also found applications of paramount importance to the world.
The pursuit of knowledge can bring pleasant surprises,
and we never know what the ideas of today
can mean to those who are going to come after us.
Last, but not the least,
Ideas grow by communicating them
clearly, systematically and without holding back.
For example, the earliest definition of a prime number
is found in a text book series called
The Elements written by Euclid in 300 BCE.
Euclid presented mathematics in these textbooks
in a rather systematic manner with the help of precise definitions,
theorems and deductive proofs.
Thanks to his passion and strong desire to compile
all the existing mathematical knowledge of his time
and present it in a systematic manner,
many people who came much later
found access to this knowledge in one place
and were able to do beautiful things with it.
Similarly in the year 1801, Gauss did to number theory
what Euclid had done to mathematics.
In his voluminous treatise,
Disquisitiones Arithmeticae, he brought together
the conceptual foundations of number theory as a discipline in itself.
The conjecture of Gauss itself stands on the shoulder of people
who came before him, who laboriously prepared
large prime tables and shared them widely.
Today in the field of education and science,
it is extremely important for us to frequently communicate
our knowledge and discoveries to the community
with the help of lectures, books, research articles and popular articles.
Ideas can grow only when we communicate them
clearly and share them viably.
Here’s to sharing and spreading lots and lots of ideas.
Thank you.