techniques to solve remainder based questions

Mostly questions in higher level aptitude consists remainder based questions. Not easy to tackle. This types of questions need a specific technique for solving. FirstofAll lets do revision of some of famous algorithm to find remainder.


1) Euler 's theorem

This theorem applies only on some condition M & N must be coprime to each other.

What is coprime numbers ?
Those numbers which have common hcf 1 is defined as coprime numbers. Therefore HCF(n1,n2,n3....) needs to be 1.

Here HCF(M,N)=1

->Take a look on problem how to solve it.

Lets say we have to find remainder of   11³⁴/12.

First, check the condition HCF(8,13)=1. If yes, then proceed

Prime Factorize 12= 2²* 3

Calculate Euler Totient Function ∅(12)= 12 (1-1/2) * (1-1/3)
                                                            = 12 * 1/2 * 2/3 = 4

So 11⁴ⁿ /12=1 (n can be any whole number)

and (11^4*8 * 11²⁾/12 =1

11³² /12=1 therefore we left with 11² /12=121/12=1

So eventually we get remainder as 1. Check your result by calculator also.



2) Fermet Theorem - Its very easy extended version of above. N must be prime and M & N should be co-prime.

->Remainder [M^N /N]= M

->Remainer [M^N-1 /N]= 1

-> M^N-M is divisible by N.

Very easy to implement, direct questions comes so apply the theorem directly.


3)  Wilson Theorem - M must be prime number

-> Remainder [(M-1)!/M]=M-1

-> Remainder[(M-2)!/M]=1


-> 11!/13 = (11-2)!/13 = 1



4) x = 1! + 2*2! + 3*3!..............10*10! 

Remainder when x+2 divided by 11!

1*1! can be written as 2! - 1!
2*2! can be written as 3!-2!
.
.
.
.
10*10! can be written as 11!-10!

After adding them we get only 11! - 1

x + 2 = 11! - 1 + 2 = 11! + 1 

(11!+1)/11! = 1

finally 1 as remainder.


Important Properties on Remainders

 5) Remainder [a*b / x ] = Remainder [a / x] * Remainder [b / x].

6) Remainder [a / x ] = 1 , then  Remainder [ a^{any power} /x ]=1

IT's all about the remainder theorems time to wrap up.


Ques - (1! + 2! + 3! + 4! + 5!)/24 what is the remainder ?

4! and 5! is divisible by 24.

so 1!+2!+3!=9/24
=9