Home » Blog » Remainders Advanced

Remainders Advanced

Friday, February 15th, 2013

---

REMAINDERS ADVANCED

 

In previous posts, we have already discussed how to find out the last two digits and basic ideas of remainders. However, there are theorems by Euler, Fermat & Wilson that make calculation of remainders easier. Let’s have a look at them.

 

Funda 1 – Euler:

 

A very common mistake that students tend to make while using Euler’s Theorem in solving questions is that they forget M and N have to be co-prime to each other. There is another set of students (like me in college) who don’t even understand what to do with the theorem or how to use it solving questions. Let us look at couple of examples in which Euler’s Theorem is used.

Note:  is also known as Euler’s Totient Function.

 

 

Funda 2 – Fermat:

If ‘p’ is a prime number and ‘a’ and ‘p’ are co-primes

 

If you notice, the three statements above are saying the exact same thing but in a different way. It is important to keep all three in mind because sometimes it becomes a little difficult to analyze which interpretation of Fermat’s little theorem is to be used.

A simple illustration of this would be:

We can check it by noticing that

Another way that you can remember Fermat’s Little Theorem (I am not joking, that is the official name – check this) is that it is a special case of Euler’s Theorem where ‘N’ is a prime number.

Because, if ‘N’ is prime then  or the Euler’s Totient Function will always be (N-1)

 

Funda 3: Wilson

Sometimes people find the history behind Wilson’s theorem to be more interesting than the theorem itself. Actually, it was know to the great Muslim polymath Alhazen approximately seven and a half centuries before John Wilson was born. Alhazen, being the great scientist that he was, never bothered to prove it and tried to regulate the floods in river Nile. After being ordered by Al-Hakim bi-Amr Allah, the sixth ruler of the Fatimid caliphate, to carry out this operation, Alhazen quickly perceived the impossibility of what he was attempting to do, and retired from engineering. Fearing for his life, he feigned madnessand was placed under house arrest, during and after which he devoted himself to his scientific work until his death.

The English mathematician, John Wilson, stated it in the 18^th century but he could not prove it either. Actually Wilson was a student of Edward Waring, who announced the theorem in 1770. None of them could prove it. Lagrange proved it in 1771. There is evidence that Leibniz was also aware of the result a century earlier, but he never published it.

I think I will end the history lesson here and continue with the mathematical part.

For a prime number ‘p’

 

Note: I have checked the related result for primes up to 120 and found it to be valid. I could not find a proof for it that I could understand. Do note that the key part of the previous sentence is not ‘find a proof for it’ but ‘that I could understand’. May be one of you can help me out in comments. J

 

I also recommend that while trying these ideas or any other remainder questions, keep Wolfram Alpha open.

---