Online CAT coaching:-
====================
Quantitative Analysis :Numbers,Remainder questions,Fermat's Theorem
---------------------------------------------------------------------------------------


Fermats theorem:-

This theorem is very important for solving the remainder questions with large powers or with large divisor. This can be used easily in solving almost all CAT level difficult remainder questions quickly.

The Theorem is as given below.on

If a & b are co-primes or relative primes and b is prime then
rem{a^(b-1)/b}=1.

If the divisor ,b is composite, then find n, the no. of co-primes between 1 and the no. Now we get rem(a^n/b) is 1.

Two relative prime numbers are those which have no common factor besides 1, such as 57 and 59], to find relative primes of number N we can use the formula N(1-1/p1)(1-1/p3)(1-1/p2)...................(1-1/pn). Where p1,p2,pn are prime factors of N.

Relative primes of 12 are 12(1-1/2)(1-1/3)=4 and those are 1,5,7,11
here 2 and 3 are the prime factors of 12.

Some practice questions are given here..

Eg.1. Find the rem(3^40/13)?

Since 3 & 13 are co-primes also 13 is prime, using Fermats theorem,rem(3^12/13)=1.So rem(3^36/13) =1.Therefore now we need to find out rem(3^4/13).
ie rem(81/13)=3.

Eg. 2. Find the rem(5^72/11)?

Since 5 & 11 are co-primes also 11 is prime, using Fermats theorem,rem(5^10/11)=1.So rem(5^70/11) =1.Therefore now we need to find out rem(5^2/11).
ie rem(25/11)=3.

Eg.3. Find the rem(5^72/12)?

Here 12 is not a prime no.
12=2^2*3.
No. of co-primes of 12 is 12(1-1/2)(1-1/3)=4.
Therefore rem(5^4/12)=1.
So rem(5^72/12)=1.

Find the Unit digit of 69^77?


What we need to find is the rem{(69^77)/10},since it will be the unit digit.
Now no. of relative primes of 10 is 10(1-1/2)(1-1/5)=4

According to Fermat's theorem,rem(69^4)/10 will be 1
Now what we do is divide the power(77) with number of relative primes(4).
So divide 77 by 4 you will get 19 remainder 1. So you are left with 69^1 divided by 10 and that is easy. So the remainder is 9 [89/10 gives 9 as remainder].
And 9 is your unit digit.

OR

But,this question can be done very easily by another method,
Use power cycle.
unit digit 9 has power frequency 2(9,1)
9 raise to any odd number is 9 only.
so the remainder(here unit digit is 9 only).