Aditya Ghosh

Number Theory has a very special place in mathematical history. In spite of having some of the easiest results to state in Mathematics, they often turn out to be some of the hardest to prove. Here’s the infamous Fermat’s Last Theorem for example. You’ve probably heard of it: 

xⁿ + yⁿ = zⁿ  has no nonzero integer solutions for n>2.

With some effort you can explain this to (almost) any high-schooler. However, proving this simple result took more than 350 years, during which it garnered the reputation of the hardest maths problem in existence as measured by having the largest number of unsuccessful proofs. Looking at the statement, it’s no wonder so many amateur mathematicians have been deceived by its innocence. Unfortunately, it would be too ambitious for me to explain to you the full proof. 

Instead, here’s another result by the great man, Fermat’s Little Theorem, which humbly says :

For any prime p, p divides (a^p – a) for all whole numbers a.

Go ahead, try to check the theorem for some small primes, like 2 and 3; or 11, if you’re feeling very confident (or have a calculator). It is a very simple statement – we can write it on a single line – but like the best of mathematics, there is beauty hidden in its simplicity. 

Over the course of 3 articles, I wish to take you on a beautiful journey of proving this result from the very beginning. We will touch some of the most fundamental areas of mathematics in the process and (hopefully) have some fun!

---

We start our long and winding journey by introducing the concept of modular arithmetic. To motivate this a bit, consider the following scenario. You’re doing an internship and the company has agreed to reimburse your food and travel costs. However, they will only reimburse daily in £10 notes and you have to pay any remaining balance at the end of each day. So, like any math enthusiast, which I’m sure you are, you want to calculate how much you have to pay out of your own pocket. 

To see how this works let’s consider an example: if you spend £26, you will have to pay £6 yourself as this is above the 2 x £10 the company will pay, but below the next increment of £10 at £30. Although it sounds quite selfish, let’s suppose it really doesn’t matter to you how much the company has to pay – all you want to know is what is the remainder, and therefore how much you have to pay, when you divide 26 by 10. That is, 6. Let’s define some notation to make it a little neater:

26 ≡ 6 (div 10)

Read this as “26 is equivalent to 6 div 10”.

Now let’s say you do this for 3 days where you spend £26, £25, £21. The total is £72 and so you have to pay £2 yourself. Let’s look at this with our new notation:

26 ≡ 6 (div 10)

25 ≡ 5 (div 10)

21 ≡ 1 (div 10)

The amateur mathematicians notice that if you add up the remainders individually they add up to £12. They slam the desk in excitement, “Aha! That itself gives the remainder 2, which is what we require!” To put it neatly :

26+25+21 ≡ 6+5+1 ≡ 2 (div 10)

You may be tempted to think this should be true in general. Instead of adding up all you owe and then finding the remainder, you can instead add up the remainders on each day and see what that is equivalent div 10. To their relief, this indeed is true. Take a moment to see what we are doing here, see if it holds for other values like £13, £22, £19.

Some of the more careful readers may want to see the proof of this and I strongly encourage them to try to figure it out themselves. (Hint : Any number n can be written as n = 10q + r where r is the remainder).

---

At the end of the third day, you get a call from the company. They are slightly annoyed that your bills are so high. They want you to refrain from extravagant restaurants and first class tickets. Maybe my advice of watching only the remainder did not work well in the real world. Forgive me, I’m but a pure mathematician.

After re-evaluating you life choices, you work out that you can manage with £12 a day. So to calculate the amount you will have to spend yourself for a period of 14 days you pull out a calculator and see 12 x 14 = 168 and 168 ≡ 8 (div 10), which means you actually have to spend £8 of your own money. The eyes of the amateur mathematicians light up. They can see a pattern here! Look closely at the numbers, can you spot it too? 

They say, “Why, 12 gives 2 and 14 gives 4 as remainders. And 12 ✕ 14 gives 8 as remainder, which is just 2 ✕ 4. You might be wondering if this is true in general (and you may want to try proving it). Using our new notation:

If: x ≡ a (div 10) and y ≡ b (div 10)

Then: xy ≡ ab (div 10)

This barrage of algebra may seem a little overwhelming at first, but not to worry, we can always think about it in words. What the statement above is saying is that instead of multiplying two numbers like 12 and 14 and then finding the remainder, you can simply multiply their individual remainders 2 and 4 and you get the same result! (8 in this case as we saw above).

Now let’s say you decide to be cheeky and try to play the system. How can you minimise the amount you have to pay? Well you can just spend £15 for 14 days. That way you obtain 0 as a remainder and you have to pay nothing at all! But you don’t want to look like a miser in front of your friends, so you might be wondering what’s the least non-zero amount you can spend. Is it £1? Does 14x ≡ 1 (div 10) have a solution? Spoiler alert, it doesn’t. The remainder in this case of 14 days can only be even. (Intuitively this makes sense, but can you prove it? The fact that both 14 and 10 are even might help). So that rules out £1. The next question is then does 14x ≡ 2 (div 10) have a solution? And this time the answer is yes (Try finding one!). 

The addition and multiplication rules that we have found above for div 10 also hold for other divisors, like div 36 or div 59. In fact they hold for any natural number like 1,2,3,… The question of whether we can find solutions to equations like ax ≡ b (div n) when a ≠ 0 in these new systems, depends entirely on the divisor n. 

If n is not prime, like the case of 10 here, we can’t find solutions for some choices of a and b. If n is prime, 5 for example, we can always find solutions for x. Take the same equation we weren’t able to solve for div 10 above but instead consider div 5 :

14x ≡ 1 (div 5)

Can you check that x = 4 is a solution?

---

In the subsequent articles we will focus on what happens when n is prime. Notice that the result: 

ax ≡ b always has a solution when a ≠ 0 

might feel eerily similar to:

 ax = b always has a solution when a ≠ 0 

But in the second case we are talking about real numbers in general, not just natural numbers. This may seem like an accident but this similarity hints at something deep and fundamental in mathematics, which we will discuss further in the next article.