You are currently browsing the tag archive for the ‘primes’ tag.

In the previous post we discussed the number of primes less than a given number and derived some very poor estimates for this quantity. In this post, using no extra technical machinery whatsoever, we derive a slightly better estimate.

Previously, we used Euclid’s proof of the infinitude of the primes as inspiration for a way of arriving at an upper bound for the number of primes less than a given number. Here, we will come up with a slightly cleverer, more quantitative proof of Euclid’s Theorem and, as before, our estimate will grow out of the proof of Euclid’s Theorem, the improvement in the bound being testament to the fact that the proof is more illuminating.

If we are prepared to accept that every number greater than one has a prime divisor, then Euclid’s famous proof of the infinitude of prime numbers is one sentence long: Given any prime number p, if I multiply together all the prime numbers less than or equal to p and then add one, I get a number which leaves a remainder of one when divided by any of the prime numbers less than or equal to p and whence has a prime divisor greater than p. I try to explain why every number greater than one has a prime divisor in this post.

Today I would like to think a little bit more about prime numbers. Specifically, we will spend some time thinking about the number of prime numbers less than a given a number. We will start by seeing if we can get any quantitative information out of Euclid’s proof itself, before moving on to cleverer ways of achieving this.

The study of  whole numbers is one of the oldest lines of inquiry in mathematics which is still thriving today. After all, it is possible in pure mathematics for the relevance of work done thousands of years ago to be undiminished today. I want to talk today about what is possibly the prototypical example of such a piece of mathematics. I am referring to Euclid’s proof of the infinitude of prime numbers.

A divisor of a number n is another, smaller number, for which there is no remainder when n is divided by it. For example, three is a divisor of six, seven is a divisor of seven and thirty-nine is a divisor of one hundred and seventeen. A prime number is a number with exactly two divisors. Let’s think about what it means to have exactly two divisors. Firstly, we observe that every whole number has at least one divisor, namely the number itself. Secondly, every whole number except for ‘1’ has at least two divisors: The number itself and the number ‘1’. So, with the exception of the number ‘1’, being prime expresses the quality of having the fewest possible divisors. Why must there must be infinitely many such numbers?

Ever wonder what happens when you send your card details over the internet? How exactly does public-key encryption work? I will write a brief, non-technical introduction to these concepts and the mathematical background in them, containing some sample code and plenty of examples.

Before we describe the RSA algorithm, there is one important mathematical concept, which is prime numbers and their factorization. Recall that a number $p$ is prime if no other number divides $p$ other than itself and $1$. For technical reasons we exclude the number $1$ from being prime. So lets see some examples. Is $3$ prime? Well, yes, no other number other than $3$ and $1$ divide it. Is $24$ prime? No, because $24 = 12 \times 2$.

There is a fundamental theorem in number theory which says that every number $n$ can be uniquely written as a product of prime numbers, i.e. $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$ where $p_1, \dots, p_k$ are prime. So again, a few examples cannot hurt. Take the number $24$. We know that $24 = 12 \times 2$, but now $12$ is not prime so $12 = 6 \times 2 = 3 \times 2 \times 2$. Hence $24 = 3 \times 2 \times 2 \times 2 = 3 \times 2^3$. That’s what a prime factorisation is, and what the theorem says is pretty basic, if a number $n = 3 \times 2^3$, then $n = 24$.

At this point now I can state what is the fundamental idea behind RSA:

Factoring a number into prime factors is much harder than checking if a number is prime!

But why is this true? There are technical reasons for this but I prefer to think along the following lines. Computers are much like humans, so imagine if a human is given the task of factorising numbers and checking if numbers are prime.