Editors note: This article contains a lot of mathematical equations, which due to the limitations of HTML have been depicted as images. If you are able to view the equations, all is well. If not, please make sure your browser is not blocking image content.
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. Lets have a look at them.
Funda 1 Euler:
Number of numbers which are less than N = ap * bq * cr and co-prime to it are,
If M and N are co-prime, that is if HCF(M,N) = 1,
A very common mistake that students tend to make while using the Eulers Theorem to solve questions is that they forget that M and N have to be co-prime to each other. There is another set of students (such as I in college) who dont even understand what to do with the theorem or how to use it to solve questions. Let us look at couple of examples in which Eulers Theorem is used.
Note: ?(N) is also known as Eulers Totient Function.
Example,
Funda 2 Fermats Little Theorem
If p is a prime number and a and p are co-primes,
If you notice, the three statements above are saying exactly the 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 Fermats little theorem is to be used.
A simple illustration of this is,
We can check it by noticing that
107 = 10000000 = 9999990+10 = 142857 ? 7 + 10
Another way that you can remember Fermats Little Theorem (I am not joking, that is the official name check this) is by observing that it is but a special case of Eulers Theorem where N is a prime number.
Because, if N is prime then ?(N) or the Eulers Totient Function will always be (N-1).
Funda 3: Wilson
Sometimes people find the history behind Wilsons theorem to be more interesting than the theorem itself. Actually, the theorem was already known 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 was instead regulating floods in the 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 madness and 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 18th 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 resume the mathematics.
For a prime number p,
Another related result to the Wilson Theorem is,
Example,
Note: I have checked the related results 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.
I also recommend that while trying these ideas or any other remainder questions, keep Wolfram Alpha open in another browser window.
Ravi Handa, an alumnus of IIT Kharagpur, has been teaching for CAT and various other competitive exams for around a decade. He currently runs an online CAT coaching and CAT Preparation course on his website http://www.handakafunda.com