Euler theorem and Fermat's Little theorem

• EXPLANATION LINK :

Euler theorem and Fermat's Little theorem

• EXPLANATION :

Euler Theoram :

If a and n are co-prime to each other then a^phi(n) ≡ 1 (mod n)

Proof :

Let us take a set , A = b₁,b₂,...,b_phi(n)(mod n) .... eq(1)

here all the intergers in the set A are coprime to n ,they are less than n,they are distinct and there are total phi(n) elements .

now let us multiply the eq(1) by a number 'a' to both sides which itself is co-prime to n and name the new set B

B = ab₁,ab₂,...,ab_phi(n) (mod n) ... eq(2) .

Now we need to proof that A and B are same Set .

so for this we need to take 3 steps .

1st step :

We are just multiplying the elements of set A by 'a' so the number of elements in A and B are same . there are phi(n) number of elements .

2nd step :

every element in A that means b_i ( 1 <= i <= phi(n) ) is multiplied with 'a' and both the numbers are co-prime with n so their product will be also co-prime ,

here 1 <= i <= phi(n)

3rd Step :

Every elements of set B is distinct . because if it is not then for any i ,j

ab_i ≡ ab_j (mod n) here 1 <= i,j <= phi(n)

=> b_i ≡ b_j (mod n) but that is not possible because all the elements in A are distinct so all the elements in B are distinct also .

Now both A and B set have equal number of elements , all the elements of both the sets are co-prime to n , they are disticnt and less than n so both the sets are actually same

so now ,

ab₁ x ab₂ x ab₃ x ... x ab_phi(n) ≡ b₁ x b₂ x b₃ x ... x b_phi(n) (mod n)

=> a^phi(n) x b₁ x b₂ x b₃ x ...x b_phi(n) ≡ b₁ x b₂ x b₃ x...x b_phi(n) (mod n)

=> a^phi(n) ≡ 1 ( mod n)

so euler Theoram is proved .

Fermat's little theoram :

if a and p are coprime and p is a prime, then a^(p−1) ≡ 1 (mod p)

it is nothing but a simple application of euler theoram ,

from Euler theoram we know already a^phi(n) ≡ 1 ( mod n )

now , if n is a prime then the value phi(p) will be p-1 ,

so , euler theoram for any prime number p that is co-prime to a will be a^p-1 ≡ 1 ( mod p )