Fermat's Theorem, Wilson's Theorem & Euler's Theorem

Sohel Sahoo : Hello guys,

Here, You will get to know about finding remainder of  tricky power of certain no. & factorials with respect to a number with some conditions & tricks to solve these sort of problems easily in competitive exams. Let's get started & be focus at these theorems to crack exams easily&grab concepts heartly with full contentment.

FERMAT’S  THEOREM:-

It states that if ‘p’ is a prime no. and ‘a,p’ are coprime no. then R[a^p-1/p ] = +1

Note:-   (i)Any number ‘p’ greater than 1 which has only two positive divisors i.e. 1 and that no.‘p’.   ‘a&p’ are said to be coprime if their gcd or HCF is ‘1’.

(ii) Here notice that the divisor p must be prime& coprime with base of power.The power is also strictly 1 less than divisor p ; then Fermat’s Theorem is applicable.

e.g. Find remainder of 2⁷² when divided by 73.

 Sol:-  Here, divisor 73 is a prime no.

 2 & 73 are also coprimes as they do not have any common divisor.

         Hence,by Fermat's Theorem the remainder is '1' .

Q. Find remainder when 2¹⁰⁶ is divided by 53.

Sol:-   Observe here, (i) 53 is a prime no.

             (ii) 2& 53 are coprimes.

              (iii) the power should be 53-1=52.But here is given 106;so convert it to multiple of 52 as shown given.

   2¹⁰⁶/53 

= (2⁵²)² x 2²/53 

= 2⁵² x 2⁵² x 4 /53 

= 1 x 1 x 4 = 4 (Ans)

 

Q. Find remainder when 5⁹¹ is divided by 31. 

 Sol:-   Observe that, (i)31 is a prime no.

             (ii) 5& 31 are coprimes.

              (iii) the power should be 31-1=30.But here is given 91;so convert it to multiple of 30 as shown given.

                                  5⁹¹/31

                                  = (5³⁰)³ x 5/31

                                   = 5³⁰ x 5³⁰ x 5³⁰ x 5/31

                                   =1 x 1 x 1 x 5 = 5

Q. Find remainder when 9¹¹¹ is divided by 11.

 Sol:-   Note that, (i)11 is a prime no.

             (ii) 9 & 11 are coprimes.

              (iii) the power should be 11-1=10.But here is given 111;so convert it to multiple of 10 as shown given.

                                   9¹¹¹/11

                                   = (9¹⁰)¹¹ x 9/11

                                   =(1)¹¹ x 9 = 9

Q. What is the remainder when 3²¹ is divided by 5 ?

 Sol:- Here, (i)5 is a prime no.

             (ii) 3 & 5 are coprimes.

              (iii) the power should be 5-1=4.But here is given 21;so convert it to multiple of 4 as shown given.

                                      3²¹/5

                                     = (3⁴)⁵ x 3/5

                                      =(1)⁵ x 3 = 3

Therefore, 3 is the required remainder.

WILSON’S THEOREM:-

The theorem can be stated as if 'p' is a prime number then;

 (i) R[(p-1)! / p] = p-1  and from this we have,

      R[{(p-1)! / p}+1] = p-1+1 = p = 0

 (ii)R[(p-2)! / p] = 1 

This theorem is a specialised case only apllicable in factorials & the condition should be obeyed.

e.g. R[15!/17] = 1 {17 is a prime no. & 17-2 =15}

       R[568!/569] = 569 -1 =568   {569 is a prime no. & 569-1 =568}

       R[(15!+25)/17] = 1+8 = 9

EULER’S THEOREM:-

According to this theorem, R[ a^Ø(N)/N ] = 1 ;

 Where (i) a &N are co-prime numbers.

           (ii) Ø(N) is called Euler Totient Function i.e. the no. of positive integers less than N that are co-prime to N.

NOTE:- Fermat's Theorem is a special case of Euler's Theorem.

Shortcut  Method to find Ø(N) :-

We can find out the value of Ø(N) by following 2 steps.

Step-1:-   Firstly, express N in terms of prime factors may be in powers of prime in factorization.

                        Let N = p₁ x p₂ x p₃ x …. And  So on.

Step-2:- Then find the value of  N{(p₁ -1)/p₁} {(p₂ -1)/p₂} {(p₃ -1)/p₃} …. And so on.

This value will be equal to Ø(N).

e.g. Ø(14) = 6

Since,the +ve integers co-prime to 14 are listed as 1,3,5,9,11&13.

Shortcut to find Ø(14) ;

Step-1:-  14 can be factorized as 14=2 x 7

Step-2:- 14(1/2)(6/7) = 6 

Ø(60) = 16

Step-1:-  60 can be factorized as 60 =2² x 3 x 5

Step-2:- 14(1/2)(2/3)(4/5) = 16  

Q. What is the remainder when 7⁸ is divided by 15 ?

Sol:-   15 = 3 x 5     [ 7&15 are coprime no.s ]

Ø(15) = 15 (2/3)(4/5) = 8

Hence, remainder is 1.

Q. What is the remainder when 2¹⁰⁰⁴ is divided by 25 ?

Sol:-   25 = 5²              [ 2&25 are coprime no.s ]

Ø(25) = 25 x (4/5) = 20

                             (2¹⁰⁰⁴ ) /25

                         = (2²⁰)⁵⁰ x 2⁴ / 25

                       = 1 x 16 =16

Hence, remainder is 16.

Q. What is the remainder when 7⁷³  is divided by 90 ?

Sol:-   90 = 2 x 3² x 5

 [ 2&25 are coprime no.s ]

Ø(90) = 90 x (1/2)(2/3)(4/5) = 24

                          7⁷³/90 = (7²⁴)³ x 7/90

                                     = 1³ x 7 =7

 Hence,remainder is 7. 

Q. What is the remainder when 9¹⁰²  is divided by 125 ?

Sol:-   125 = 5³

 [ 9&125 are coprime no.s ]

Ø(125) = 125 x (4/5) = 100

                          9¹⁰²/125 

                         = 9¹⁰⁰ X 9² /125

                          = 1 x 81 = 81

 Hence,remainder is 81.

Q. What is the remainder when  13¹⁹⁴  is divided by 360 ?

Sol:-   360 =  5x3²x2³

 [ 13&360 are coprime no.s ]

Ø(360) = 360 x (1/2)(2/3)(4/5) = 96

                          13¹⁹⁴/360 

                         =  (13⁹⁶)²X 13² /360

                          = 1² x 169 = 169

 Hence,remainder is 169.

Hope,these concepts will enhance your thinking ability to the different questions. Do solve these problems repeatitively to hold the concept in your mind for a long time.