Remainder questions can be broadly divided into 2 types...
1). LCM based questions. e.g. a no. leaves remainders 3,2 when successively divided by 5,6...what will be the remainder when this no. is divided by 30?
2). Power based questions. e.g. remainder when (31)^[(373)^(432)] is divided by 7.
we have already discussed type 1 in two parts...those who have missed it or wish to revisit the concept may use the link below.
first half
http://www.pagalguy.com/forum/quanti...-fundas-2.html (Concepts...total fundas!!)
second half
http://www.pagalguy.com/forum/quanti...-fundas-5.html (Concepts...total fundas!!)
so what we're left to discuss is type 2 mentioned above...i think there are 3 ways of solving these questions...v gotto use our own sensibility to c which approach suits where...
a) Using binomial theorem
b) using cyclicity with remainders
c) using euler's theorem.
for better understanding, i'll divide this post into 3 parts...n will discuss one approach in each part...
Finding remainders using binomial theorem.
(x+y)^n can be expressed as :
nC0 x^n + nC1 x^(n-1)y^1 + nC2 x^(n-2)y^2 + .......... nCr x^(n-r)y^r + ..... nCn y^n
concept:
first term, i.e nC0 x^n is the only term that is independent of y and last term, i.e nCn y^n is the only term that is independent of x. rest, all the terms are divisible by both x & y.
we'll leverage this property to solve complex problems.
e.g. 28^37 % 9 = ?
see...v can express it as (27 + 1 )^37 % 9. now, since 27 is a multiple of 9, the only term that'll be independent of 9 will be the last term i.e. nCn 27^0 * 1^n = 1.
hence, the remainder is 1%9 = 1.
important observation:
we know 1^ (any damn thing...even infinity) = 1 and (-1)^(anything) = 1 or -1 with even and odd values of power respectively. so we'll try getting a form of (nD +/-1)^N. so that v r ultimately left with (+/-1)^N.
342^423 % 7 = ?
step1:
342%7 = 6.
so the question becomes...
6^423 % 7.
express 6 as 7 - 1.
so the expression becomes...
(7-1)^423.
the only terms independent of 7 is ... -1^423 = -1.
hence, the remainder is -1 + 7 = 6.
523^325 % 7 =?
=> 5^325 % 7.
now, i seek a remainder of 1 or 7-1=6 with a power of 5.
5^1 % 7 = 5....wont work
5^2 % 7 = 4....wont work.
5^3 % 7 = 6...will work.
so, (5^3)^ (325/3) = (5^3)^ (108 ) x 5
= (-1)^108 x 5
= 1x5 =5...the remainder.
529^700000 % 7
= 4^700000
4^3%7 = 1. hence, we'll express the given expression in terms of 4^3
4^3 ^ (700000/3)...c how to save time...700000%3 = (7 + 0 + 0 + 0 + 0 + 0) % 3 = 1. hence (700000-1)/3 will be an integer...dont evaluate its value... bcoz 1^ anything = 1.
hence v have 1^I x 4^1 = 1 x 4 = 4
therefore, the remainder is 4.
(31)^[(373)^(432)] % 7 = ?
31 % 7 = 3
hence,
=(3)^[(373)^(432)]
3^3 = 27 = 28 -1. hence, expression shud be in terms of 3^3
= 3^3 ^ [(373^432)/3]
now treat [(373^432)/3] as a new, different question...
(373^432)%3 = 1.
hence, the term becomes 3^3^(I) x 3^1
I = (373^432 - 1)/3 and is of the form (odd-odd) / odd = even/odd = even for sure!!
hence, the expression becomes....
(3^3)^(even I) x 3 % 7
= (-1)^even integer x 3 = 1 x 3 = 3
hence, remainder = 3.
case when divisor is a large no.
in such questions, v try to reduce power by increasing the value of base and bringing it close to a multiple of divisor.
e.g. 2^35 % 61 = ?
v know 2^6 = 64
hence, (2^6)^5 x 2^5
2^6 % 61 = 3.
hence, 3^5 x 2^5
= 3^4 x 3 x 2^5
=3^4 % 61 = 20.
3x 2^5 = 96, 96%61 = 35.
hence, 20 x 35 % 61 = 700%61
= 29, the reqd answer.
Finding remainders using cyclicicty with remainders:
This approach is useful when the divisor is small or at times when it is a factor of 100.
3^327%7 = ?
3^1 % 7 = 3
3^2 % 7 = 2
3^3 % 7 = 6
3^4 % 7 = 4
3^5 % 7 = 4x3 % 7 = 5
3^6 % 7 = 5 x 3 % 7 = 1
3^7 % 7 = 1 x 3 % 7 = 3
remainder with first power is same as remainder with 7th power...hence v can say that cyclicity in remainders is 7-1 = 6.
so, 327 % 6 = 3,
hence, effectively, the remainder is 3^3 % 7 = 6
326^524 % 9 =?
326 % 9 = 2
hence, 2^524
now,
2^1 % 9 = 2
2^2 % 9 = 4
2^3 % 9 = 8
2^4 % 9 = 7
2^5 % 9 = 5
2^6 % 9 = 1.
2^7 % 9 = 2
hence cyclicity in remainder = 7-1 = 6.
524 % 6 = 2
hence, the remainder is 2^2 % 9 = 4.
81^502 % 100
81^1 % 100 = 81
81^2 % 100 = 61
81^3 % 100 = 41
81^4 % 100 = 21
81^5 % 100 = 01
81^6 % 100 = 81
hence, cyclicity = 6-1 = 5.
502 % 100 = 2.
so the reqd remainder is same as that with 81^2 = 61.
similarly...this method can be effectively used when remainders are other factors of 100.
viz, when the factors are 20,25,50,100...knowing last 2 digits wud suffice knowing the remainders...we've already discussed this concept while discussing cyclicity...
important: dont try this method when the divisors are complex...viz 37,73 etc...the cylicty wud come very late n calculations will grow cumbersome...when divisors are complex, there must be sum other catch in the question...look for that catch...e.g. last type discussed in the binomial method...
This approach is useful when the divisor is small or at times when it is a factor of 100.
3^327%7 = ?
3^1 % 7 = 3
3^2 % 7 = 2
3^3 % 7 = 6
3^4 % 7 = 4
3^5 % 7 = 4x3 % 7 = 5
3^6 % 7 = 5 x 3 % 7 = 1
3^7 % 7 = 1 x 3 % 7 = 3
remainder with first power is same as remainder with 7th power...hence v can say that cyclicity in remainders is 7-1 = 6.
so, 327 % 6 = 3,
hence, effectively, the remainder is 3^3 % 7 = 6
326^524 % 9 =?
326 % 9 = 2
hence, 2^524
now,
2^1 % 9 = 2
2^2 % 9 = 4
2^3 % 9 = 8
2^4 % 9 = 7
2^5 % 9 = 5
2^6 % 9 = 1.
2^7 % 9 = 2
hence cyclicity in remainder = 7-1 = 6.
524 % 6 = 2
hence, the remainder is 2^2 % 9 = 4.
81^502 % 100
81^1 % 100 = 81
81^2 % 100 = 61
81^3 % 100 = 41
81^4 % 100 = 21
81^5 % 100 = 01
81^6 % 100 = 81
hence, cyclicity = 6-1 = 5.
502 % 100 = 2.
so the reqd remainder is same as that with 81^2 = 61.
similarly...this method can be effectively used when remainders are other factors of 100.
viz, when the factors are 20,25,50,100...knowing last 2 digits wud suffice knowing the remainders...we've already discussed this concept while discussing cyclicity...
important: dont try this method when the divisors are complex...viz 37,73 etc...the cylicty wud come very late n calculations will grow cumbersome...when divisors are complex, there must be sum other catch in the question...look for that catch...e.g. last type discussed in the binomial method...
Finding remainders using Euler's theorem.
(special thanks to junoonmba for this)
This method is very useful when the divisor and dividend are relatively prime numbers...
step 1: To calculate euler's no. of a divisor.
euler's no. can be practically taken as cyclicity in remainders by a divisor..
to find euler's no, express the divisor in terms of prime factors...
100 = 2^2 x 5^2.
powers of the prime nos. have no significance...its jus the prime no. that matters...
euler's no (e for convenience) = divisor x (1-1/first prime factor) x (1-1/second prime factor) x ... (1-1/last prime factor)
so, for 100, e = 100 x (1-1/2) x (1-1/5) = 100 x 1/2 x 4/5
= 40.
that means e for 100 = 40. or, in other words, 100 divisor will definetly show a cylicity of 40 in the remainders.
whenever the power of a relatively prime no. will be a multiple of 40, the expression wud show a remainder 1 with 100.
e.g. 3^120 % 100 = ?
we know e for 100 = 40.
3 n 100 are relatively prime nos.
hence, 3^40 % 100 = 1.
hence 3^120 % 100 = (3^40)^3 % 100 = 1^3 = 1.
7^100 % 45 = ?
45 = 3x3x5
e for 45 = 45 x (1-1/3) x (1-1/5) = 24
hence, 7^24 % 45 = 1
hence, 7^100 % 45 = 1^4 x 7^4 % 45
= 2401 % 45
= 16, the required answer...
(special thanks to junoonmba for this)
This method is very useful when the divisor and dividend are relatively prime numbers...
step 1: To calculate euler's no. of a divisor.
euler's no. can be practically taken as cyclicity in remainders by a divisor..
to find euler's no, express the divisor in terms of prime factors...
100 = 2^2 x 5^2.
powers of the prime nos. have no significance...its jus the prime no. that matters...
euler's no (e for convenience) = divisor x (1-1/first prime factor) x (1-1/second prime factor) x ... (1-1/last prime factor)
so, for 100, e = 100 x (1-1/2) x (1-1/5) = 100 x 1/2 x 4/5
= 40.
that means e for 100 = 40. or, in other words, 100 divisor will definetly show a cylicity of 40 in the remainders.
whenever the power of a relatively prime no. will be a multiple of 40, the expression wud show a remainder 1 with 100.
e.g. 3^120 % 100 = ?
we know e for 100 = 40.
3 n 100 are relatively prime nos.
hence, 3^40 % 100 = 1.
hence 3^120 % 100 = (3^40)^3 % 100 = 1^3 = 1.
7^100 % 45 = ?
45 = 3x3x5
e for 45 = 45 x (1-1/3) x (1-1/5) = 24
hence, 7^24 % 45 = 1
hence, 7^100 % 45 = 1^4 x 7^4 % 45
= 2401 % 45
= 16, the required answer...
Some Questions
1). 4^32 % 36
2) 312^[(124)^(312)] % 7
3) 532^[(325)^(534)] % 7
4) 7^200 % 11
1.Remainder of 26^16 divided by 125
2. Remainder of 3^94 divided by 125
3.Reamainder of 2^13 divided by 25
4. Remainder of 10^14 divided by 37
5 2^1990%1990
2) 312^[(124)^(312)] % 7
3) 532^[(325)^(534)] % 7
4) 7^200 % 11
1.Remainder of 26^16 divided by 125
2. Remainder of 3^94 divided by 125
3.Reamainder of 2^13 divided by 25
4. Remainder of 10^14 divided by 37
5 2^1990%1990
2^2!^3!^4!...100! %
1. 7
2. 9
3. 5^32 % 5000
4. 2^60 % 130
5. 7^50 % 1001
1. 7
2. 9
3. 5^32 % 5000
4. 2^60 % 130
5. 7^50 % 1001
* source pagalguy
No comments:
Post a Comment