Fermat's Little Theorem

Before reading through this post it is useful if you have some knowledge of modular arithmetic.

Fermat's little theorem (it's 'little' because of Fermat's comparatively more difficult to prove last theorem, not because it is less useful, in fact it is more useful) is a vital result from the field of number theory as it provides a method of checking (within reason) whether a number is prime or not. Also it is a very interesting result that utilises modular arithmetic.

Fermat's little theorem is that given a prime number, p, and any integer, a, a^p - a will divide by p to give an integer value. Or, more mathematically, p|a^p - a. So from the definitions in modular arithmetic this means that a^p ≡ a (mod p); it can also be wrote as a^p-1 ≡ 1 (mod p) - both are equally valid but the second is used more often mainly because it has a 1 on the right hand side and this is 'neater' and mathematicians love things to be neat!

There is a condition for the integer a and that is that it is coprime to p. Coprime means that the highest common factor between two numbers is 1; so for example 3 and 46 are coprime as the only factor they have in common is 1. The reason for why a must be coprime to p will come later.

When Pierre de Fermat first stated this theorem in a letter to his friend (in 1640) he did not include a proof of why this is the case as it was "too long". To attempt to 'one up' one of the greatest mathematicians in the past 400 years I will include a proof of this fact.

There are three points of contention within this proof that I feel I should justify/explain further. (A) is that these numbers are chosen intelligently in order to prove Fermat's little theorem, this was not the original proof of the theorem as it is difficult to be able to choose these numbers initially but in hindsight it is clear that these work very well.

(B) requires further explanation. The reason that when a, 2a, 3a,..., (p - 1)a are divided by p will give remainders 1, 2, 3,..., (p - 1) in some order is because of Euclid's lemma, if a prime number divides the product of two numbers then the prime number must divide at least one of the factors. Clearly none of the numbers in list A can be divided by p (a is coprime to p), so some integer in the range of list B, n, is coprime to p too - this means that na can not be divided by p so this means that a, 2a, 3a,..., (p - 1)a when divided by p must have remainders in the region of 1, 2, 3,..., (p - 1). Read more on this.

For (C) why can we cancel out (p - 1)! in modular arithmetic? It isn't an equals sign after all. If we consider ax ≡ ay (mod n), this means that ax - ay can be divided by n, factorising this we get a(x - y) can be divided by n implying that either a can be divided by n or x - y can be. In our case a is (p - 1)!, x is a^{p - 1} and y is 1; but (p - 1)! is clearly coprime to p so that means that a^{p - 1} - 1 can be divided by p so we can in fact cancel the (p - 1)!s.

And that is Fermat's little theorem fully proved! You will have almost certainly encountered Fermat's little theorem whether you knew it or not, almost all online security and encryption utilises prime numbers to stop data being intercepted and Fermat's little theorem is used to check the primality of numbers to be used.

If you do not understand anything in this post, feel I have made a mistake or need extra explanation on anything covered here leave a comment and I will get back to you as soon as I can.

Proof by Contradiction: Infinite Prime Numbers

There are many complex and obscure methods of proving that there are infinite prime numbers, but this one is certainly the easiest and it is a demonstration of how unpredictable numbers can be dealt with in an efficient manner, it is also an easy introduction to proofs by contradiction.

First, just to clarify what proof by contradiction actually means:
1.) We assume that what we are trying to prove to be false is in fact true.
2.) If we find a contradiction in our assumed hypothesis that we have assumed then it can not be true. And that means that our assumed hypothesis is false, proving what we originally wanted.

So using this as our basis we are going to assume that there is in actual fact a finite amount of prime numbers, how many there is does not matter just that at some point there are no more prime numbers. If we multiply all of these prime numbers together we will get:

2 × 3 × ... × p_n-1 × p_n

Where p_n is the last prime number and this number is clearly not prime as is has every single prime number as a factor. However if we add 1 to this number then any of the prime numbers that we try to divide it by will give a remainder of 1, this means that it too is prime!
p = 2 × 3 × ... × p_n-1 × p_n + 1

If this number is also prime it means that our original statement about there being finite prime numbers is incorrect, therefore there are an infinite number of prime numbers!

This took literally two lines of working to prove that there are an infinite number of prime numbers, this massive, beautiful and unfathomable concept was proved so efficiently and beautifully. This is what Maths is about, how concisely you can express complicated statements. Maths is solely about explaining the world around us and where this leads us is some amazing, incomprehensible places.

Riemann Hypothesis

Now I am definitely not an expert in this field, and in fact even the experts aren't really experts in the conventional sense. No one is an expert on it in the conventional sense, it is still unsolved. Over 150 years old and it still remains unsolved not for the lack of trying! In fact it is so important to mathematicians that the Clay Mathematics Institute has put a $1,000,000 bounty on its head (that is, you get $1,000,000 if you manage to solve it).


But what actually is the Riemann Hypothesis? It is a conjecture about the location of the non-trivial zeros of the Riemann Zeta function, it states that all the zeros should lie on the critical strip 0.5+it. "Oh yeah!", I hear you cry, now you get it, obviously. I will explain what this means properly later on in this post. But first I will state what it means. If true it implies a lot of things about the distribution of prime numbers, and as you may or may not know they are very irregular and very difficult to find as the numbers get very, very big.


To track back to my earlier point, what is the Riemann Zeta Function ( it is denoted as ζ(s), ζ being the Greek lower case from which z was derived)?

Where s is an imaginary number, a+ib.

This requires that you understand sequences and series, imaginary numbers and imaginary exponents. The real intrigue of this comes from the fact that it can be represented by Euler's product.

As you may or may not notice this is comprised of the prime numbers, this means that there is a sort of subliminal link between the natural numbers and the prime numbers. This showed that the prime numbers were not just positioned randomly and are not merely the building blocks to numbers but there is an actual link between them and the natural numbers.


The Riemann Zeta Function on its face doesn't look too difficult, I mean it is just an infinite sequence, even with a complex power you'd expect this to be possible and even pretty easy. But that is not the case at all, part of the reason is how sporadic complex exponents can be, and although it is not too difficult to find solutions (using a high powered computer thousands can be found each hour) it is incredibly, incredibly hard to find a proof for all the solutions.

The plot of the Riemann Zeta Function, the red line is the
real part, the blue part is the imaginary part.

You can see, this function seems to have little to no consistency to it, but a fair amount is known about the function. A lot of the zeros do actually satisfy the hypothesis, over 10 trillion of them in fact. And you'd think that is a proof alone, but as it often involves an iterated log (a log of a log, log(log(x)) and this increases very, very, very slowly in fact log(log(10,000,000,000)) = 1, so 10 trillion really isn't anything. If it is still holding true for log(log(x))>40 there may be a greater unanimous opinion on the truth of the hypothesis.


Every mathematician worth his salt has had an encounter with the Riemann Hypothesis and it has withheld every single attempt thus far. The maths used to try and tackle the problem is so complex that entirely new branches of mathematics have been created to deal with it, this maths to laymen has literally nothing, at all, to do with the prime numbers. It is so complex and far away from the problem that it almost boggles mathematicians minds, but it consumes them, it is their passion and life.


Prime numbers are the passion for many and the Riemann Hypothesis is merely an extension of that, and hopefully it will be solved in my life time.


If you have caught the prime number bug I suggest you read the excellent book by Karl Sabbagh called Dr Riemann's Zeros.

Perfect Numbers

This, truly is a definition of eloquence. One for its rarity and two for the fact that the numbers are in fact, perfect. But why are they perfect? They do not hold the key to the mysteries of the universe (as of 3rd March 2011!), they are just a phenomena that intrigues Mathematicians (an intrigue that started as early as 100AD). But, what is a perfect number? It is a number where all it's divisors (excluding the number itself) add to make the original number. They are incredibly rare however, and I believe that is the source of their intrigue.

Perfect Numbers and Mersenne Primes (I have touched on these before) go hand in hand, so hand in hand that the formula for finding Perfect Numbers requires Mersenne Primes. Euclid discovered that 2^p−1(2^p−1) where 2^p−1 is prime, a Mersenne Prime in fact, will always reveal a Perfect Number. There is currently 47 Perfect Numbers known, the same amount as there is Mersenne Primes; obvious because Perfect Numbers rely on Mersenne Prime numbers.

Perfect numbers increase at a rather rapid rate, as you can see: 6; 28; 496; 8128; 33,550,336, 8,589,869,056; 137,438,691,328; 23,058,43,008,139,952,128. And the highest known perfect number has 25,956,377 digits, which is huge.

It is still unknown whether or not there is infinite Mersenne Primes and thus Perfect Numbers, it is also not known if there is any odd perfect numbers, if you would like to read more on this visit here: http://mathworld.wolfram.com/PerfectNumber.html