# 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.
IIM CAT Preparation Tips: Fermat's Little Theorem and Euler's Phi function

## Nov 15, 2010

### 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.