Posted by: Eoghan | August 1, 2008

## Fermat’s Fermaths

First in series.

Let me first thank the people of Wikipedia for creating a great way of providing footnotes for interested readers.

You may have heard of a mathematical idea called Fermat’s Last Theorem. Pierre Fermat, a famous French mathematician of the 17th century claimed to have a proof (but never published one) that there were no whole numbers such that the cube of one was the sum of the two others’ cubes and that the same held for fourth powers and fifth powers and so on, every power in fact except squares. So 3^2 + 4^2 = 9 + 16 = 25 = 5^2 but there is no trio of numbers like (3, 4, 5) where you could do the same thing with their cubes.

Anyhoo, this problem is fairly simple to state but defied the attempts of history’s greatest mathematicians to solve it until 1995 when an English professor called Andrew Wiles proved it as a consequence of a much broader truth.

Pierre de Fermat

Less well known but almost certainly more relevant to your life is Fermat’s Little Theorem. This fact is used as part of the most common encryption technique for electronic data, known as RSA. So every time you make a secure credit card purchase online you are probably enjoying the benefits of this result.

The theorem deals with prime numbers, which you might remember from school are numbers divisible only by themselves and one. So 7 is prime but 6 is not, since 6 = 2 * 3.

It also features “powers” or exponents. If you multiply a number, say 3, by itself you can write 3*3 or 3^2 where ^2 means “to the power of two”. 3*3*3 is 3^3 which is “3 to the power of 3”, 3*3*3*3 = 3^4, “3 to the power of 4” and so on.

Now we’re ready for the punchline. Fermat’s Little Theorem says that if p is a prime number and a is any whole number that p doesn’t divide cleanly (i.e, without a remainder) then, if you raise a to the power of p-1 and then divide by p, you get a remainder of 1 no matter what exact numbers a and p are. For example, let a=8 and p=3. a^(p-1) = 64 and 64/3 is 21 remainder 1. But also, if a=18 and p=5 then a^(p-1)=104976 and 104976/5=20995 remainder 1. Try it yourself with any prime you like and any whole number that your prime doesn’t divide evenly.

That’s all lovely I think you’ll agree but you’re no doubt eager to see how that helps make a code.

Watch this space…