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.

Challenge Question 1: Solutions

This is the worked solution to Challenge Question 1.

To begin thinking about the problem it is a must to visualise or draw out what is actually going on and begin labelling what we know.

As all that matters in this question is the ratio from side to side we can say that the largest square has a side length of 1, the next is 1/2, the next 1/4, etc. This means that the area of the first square is 1, then next is 1/4, the next 1/16, etc.

You can see that there is a ratio of 1/4 between the area of a square and the square before it. So to find the total area of all the squares you can use the formula for the sum of an infinite geometric series a/(1 - r) (explained here), multiply it by 4 (for each branch) and then add 1 (for the central square). So we get [4 × 0.25/(1 - 0.25)] + 1, which gives a total area for the squares as 7/3.


Now for the area of the shaded squares. The first shaded square has a side length of 1/4, so it has an area of 1/16, the next shaded square has a side length of 1/8 and an area of 1/64. You can see that the ratio from the area of one square to the next is 1/16. The total area of the shaded squares uses the sum of an infinite geometric series again and multiplies it by 4 (for each branch). So we get 4 × 0.125/(1 - 1/16), which equals  8/15.


So the area of all the overlapping squares is 8/15 and the total area of all the squares is 7/3, so the proportion of the shaded squares is 8/15 ÷ 7/3 = 0.22857142857... So the final answer is that the shaded squares occupy 22.86% of the total area of the squares.

SOLVED: Challenge Question 2

If you are the first to solve this problem I will give you complete set of the Richard Feynman Lectures on Physics (read up upon the Feynman Lectures on Physics).

Question:

A man, who is 1.65m tall, wishes to find the height of a tree with a shadow 36.52m long. He walks 24.12m from the base of the tree along the shadow of the tree until his head is in a position where the tip of his shadow exactly overlaps the end of the tree top's shadow. How tall is the tree? Round to the nearest hundredth.

Leave answers either in the comments box or contact me with the answer through our contact page or email me at rouge.ray@gmail.com.