Fermat’s Little Theorem and Euler’s Phi function

Fermat’s Little Theorem states that if p is prime then a^p – a is a multiple of p. In other words,

a ^ (p-1) = 1 mod p, whenever a is not a multiple of p
The proof for this theorem is interesting. Take any number a that is co-prime with p. Now, a will correspond to some r (mod) p, where r lies between 1 and p-1
Now, take the numbers a, 2a, 3a, 4a, 5a,…(p-1)a…All these numbers will be co-prime with p (as p is prime) and all will leave remainders from 1 to p-1. Let us assume they leave remainders r, r2,r3,r4, …rp-1. Now, none of these remainders will be equal to 0. Importantly, no two of these remainders can be equal.
(This is a critical result, which is established below)
Suppose r3 were equal to r5. Then, 5a -3a would be a multiple of p => 2a is a multiple of p, which is impossible.
This implies r, r2,r3,r4, …rp-1 should correspond to 1,2,3,…p-1 in some order.
Now, when we multiply a, 2a, 3a, 4a,…(p-1)a in modular arithmetic terms, we should get a remainder of 1*2*3*…(p-1)
Or, a p-1 * 1*2*3*…(p-1) = 1*2*3*…(p-1) mod p
Let us say 1*2*3*…(p-1) = X
Or, a p-1 * X = X mod p
Or, X (a p-1 -1) = 0 mod p
Now, X cannot be 0 mod p, so, a ^ (p-1) has to be 1 mod p, which is Fermat’s Little Theorem
Now, for Euler’s Phi function and Theorem.
Euler’s Phi function states that
 
For two numbers m,n that are coprime (HCF of m,n =1)
m phi(n) = 1 mod n, (m phi(n) leaves a remainder of 1 when divided by n)
Now, m and n are co-prime numbers. The possible remainders that m can have when divided by n are numbers from 0 to n-1 that are co-prime to n. A set that has phi(n) elements. We have seen this result here .
Now, let the elements in that set be R1 R2,R3,R4, …Rp set of possible remainders that m can leave when divided by n. This implies that p = phi(n).
Now, let us assume that m leaves a remainder R on division by n, R belongs to the above mentioned set.
Let us take the numbers R1 * m, R2 * m, R3 * m,R4 * m, …Rp * m. Now, none of these would correspond to o mod n. Importantly, no two of these can be equal mod n either.
Because if R4 * m and R7 * m were equal mod n, then m *( R4 – R7) would be a multiple of n, which is impossible.
Therefore, the numbers R1 * m, R2 * m, R3 * m,R4 * m, …Rp * m should correspond to the numbers R1 , R2 , R3 ,R4, …Rp mod n in some order.
Now, if we take the product of the p numbers R1 * m, R2 * m, R3 * m,R4 * m, …Rp * m. This will be equal to R1 * R2 * R3 * R4* …* Rp mod n.
Let R1 * R2 * R3 * R4* …* Rp = Y
mp Y = Y mod n
Y (mp-1) = 0 mod n
Or, mp = 1 mod n
m ^ phi(n) = 1 mod n, which is Euler’s Phi Function.
Brilliant Theorem. Beautiful implications. But, I dont think CAT will have a question based on this theorem.
In the same ‘too tough for CAT category’ one can file Wilson’s theorem as well.

Related posts

  • Number Theory – Euler’s Phi FunctionNovember 15, 2010 Number Theory – Euler’s Phi Function Euler's phi function is an important property in Number Theory. But before we go in any detail into this topic, let me clarify that it is very unlikely that a CAT question will require […] Posted in Number Theory
  • CAT Number Theory – ModulusNovember 15, 2010 CAT Number Theory – Modulus Had sent an entry on Euler's phi function earlier , and thought it would be best to follow this up with a slightly more detailed post on modulus arithmetic. If we divide a number N by […] Posted in Number Theory
  • Wilson’s Theorem for CATSeptember 22, 2015 Wilson’s Theorem for CAT Wilson's theorem states that for any prime number 'p', (p-1)! divided by p leaves a remainder of p - 1. In other words, 16! divided by 17, remainder is 16. 12! divided by 13, […] Posted in Number Theory
  • Permutations and CombinationsNovember 5, 2012 Permutations and Combinations Question Sum of three whole numbers a, b and c is 10. How many ordered triplets (a, b, c) exist? (This is a variant on the previous question that can be found here). Will post the […] Posted in Combinatorics

One comment

Leave a Reply

Your email address will not be published. Required fields are marked *