Latest Elitmus Aptitude Question SOLUTION: wht is remainder when 128^1000 is divided by 153..?

128^1000/153 = 128^1000/17.9

now when 128^1000 is divided by 17 rem

2^7000/17 = 16^1750/17 = (17-1)^1750/17 so rem = 1

it can be represented by 17a +1.............(1)

when 128^1000 is divided by 9

2(3*333 + 1)mod9 = -1*2mod9 = 7mod9 so rem = -1.2 = -2 = 7

it can be represented by 9b + 7............(2)

equating (1) and (2)

17a+1=9b+7 => 9(b-a) = 8a - 6
this is true for a = 3

so remainder = 17*3 +1 = 52

128^1000 = (153-25)^1000 = (25^1000)mod153 = (625^500)mod153 = [(4*153+13)^500]mod153 = (13^500)mod153 = (169^250)mod153 = [(153+16)^250]mod153 = (16^250)mod153 = (256^125)mod153 = [(153+103)^125]mod153 = (103^125)mod153
= [(2*3*17+1)^125]mod153

At this point,observe that 153=17*(3^2);

Now,therefore clearly (2*3*17+1)^125 = [(125C124)*{(2*3*17)^1}*(1^124)+1]mod153.

Actually,the above line can be written since only except the last two

terms,every term of the expansion of (2*3*17+1)^125 has [(2*3*17)^2],i.e,

[153*68] as one of its factors.

Now, [(125C124)*{(2*3*17)^1}*(1^124)+1]= 125*2*3*17 + 1;

[125*2*3*17 + 1]/(153) = [125*2*3*17 + 1]/(3^2*17) = (125*2*3*17)/(3^2*17) +

1/(3^2*17) = 250/3 + 1/(3^2*17) =83 + (1/3)+ 1/(3^2*17) = 83 + (52/153);

which means [125*2*3*17 + 1] = 83*153 + 52;

which again implies 128^1000 = [125*2*3*17 + 1]mod153 = {83*153 + 52}mod153 =

52mod153 ;

So, remainder is 52.

52 is the remainder.


128^1000 / 153
proceed this prob as previous 1 which u asked,
128^1 = -25 mod(153) i.e. 128-153
128^2= (-25)^2 = 625 mod 153 = 13
128^4 = 13^2 = 169 mod153 = 16
128^8 = 16^2 = 256 mod 153 = 103
128^16 = 103^2 = 10609 mod 153 = 52
128^32 = 52^2 = 2704 mod 153 = 103
128^64 = 103^2 = 10609 mod 153 = 52
128^128 = 52^2 = 2704 mod 153 = 103
128^256 = 103^2 = 10609 mod 153 = 52
128^512 = 52^2 = 2704 mod 153 = 103
finally for 128^1000 we can re-write it as : 128^512 * 128^256 * 128^128 * 128^64*128^32 * 128^8
which is equals to
= > { 103 * 52 * 103 * 52 * 103 * 103 } mod 153
=> 103 ^2 Mod 153 * 52* 52 * 103 * 103
= > 52 *52*52* 103 ^2 Mod 153
=> { 52 * 52*52* 52 } mod 153
= > 52^2 mod 153 * 52^2
= > 103 * 103 mod 153 ( i.e. similarly for 52^2 mod 153 = 103)
= > 52 .

@ ANKUR TRIVEDI :

You are most welcome & thanks a lot to u too.I'm really feeling honored due to

the fact that I've got at least some1 who,expending a considerable amount of

his valuable time, have noticed and most importantly acknowledged the solution

I've posted.

I'm really feeling gratified due to your precious feedback.

Thank u soo much 1ce again..:-):-)

@ Sdeep Bhattacharya:
yes you gives a very nice solution,but at the time of paper we have not enough time for doing this big solution,and also time consuming.
is there are shortcut method for doing this type of questions?

153 = 32*17 = 9*17

and 1281000 = 21000mod9 = 2(3*333 + 1)mod9 = -1*2mod9 = 7mod9.

also 1281000 = (-8)1000mod17 = 23000mod17 = 24*750mod17 = 1mod17.

Also 9*2 - 17*1 = 1

Using Chinese Remainder Theorem

128^1000 = (9*2*1 - 17*1*7)mod153 = -101mod153 = 52mod153
This is simply application of Chinese Remainder Theorem.

For two divisors D1 and D2 such that HCF(D1 , D2) = 1, first find integers x, y so that xD1 + yD2 = 1

Next let N ≡ r1 mod D1

and also N ≡ r2 mod D2

Then according to Chinese Remainder Theorem (CRT):

N ≡ (xD1r2 + yD2r1) mod D1D2. so answer wud be 52

We have to find out Rem [128^1000/153]

This looks a little difficult if you do not any theorems for finding out remainders. Let us take a simpler approach and break down the problem into smaller parts.

These type of questions become really simple if you understand the concept of negative remainders. Always try and reduce the dividend to 1 or -1.

153 = 9*17
128^1000 = 2^7000

Let us find out Rem[2^7000/9] and Rem[2^7000/17]
We will combine them later.

Rem[2^7000/9]
= Rem [ 2^6999 x 2 / 9]
= Rem [ 8^2333 x 2 / 9]
= Rem [ (-1)^2333 x 2 / 9]
= Rem [ (-1) x 2 / 9]
= - 2 from 9
= 7

Rem[2^7000/17]
= Rem [16^1750 / 17]
= Rem [ (-1)^1750 / 17]
= 1

So, our answer is a number which leaves a remainder of 7 when divided by 9 and it should leave a remainder of 1 when divided by 17.

Let us start considering all numbers that leave a remainder of 1 when divided by 17
=> 18 (leaves a remainder of 0 from 9. Invalid)
=> 35 (leaves a remainder of 8 from 9. Invalid)
=> 52 (leaves a remainder of 7 from 9. Valid. This is our answer)

I have answered a bunch of very similar questions on remainders. You can get the complete list here: Remainder Theorem and related concepts for CAT Preparation by Ravi Handa on CAT Preparation

first of all we will write 128^1000 =(128^2)^500.ie 16384^500.
now in this type of case we divide power by 4 and check the remainder.when we will divide 500 by 4 then remainder will be zero.so .we will divide 16384 by 153.and take the remainder.so remainder will be 13.

SDeep Bhattacharya ,thank you for detail.now i am agree with you.

This is so awesome question....in this we have to divide 153 as a product of 2 coprime numbers i.e 17*9
now we will calculate 2^1000/9 and 2^1000/17 leaves the reaminder 16 and 7 respectively
let N= 2^1000
so now N=17 a+16
and N=9b+7
so checking for values of 17a+b that willl give remainder of 7 when divided by 9
so i.e 16 so general for of number is N=153*a+16

153=17*9
divide 128^1000 by both individually

128^1000/9=(2+126)^1000/9=2^1000/9
remainder for this is 7

128^1000/17
Note:For any prime number , k^p-1/p leaves remainder 1,here 128^16/17 would leave remainder as 1.
hence 128^1000=128^8/17=9^8/17 =13^4/17 =1

9x+7=17y+1
x=5 satisifes
hence 52

(8^4)/153=84

cool answer guys,,,,
but according to me the solutions is something like....
(128)^(20*50)......ie remindr of (any no)^20 = 00 ie its circle gets completed
thus 128 is the answer
;)

I am using the concept of Euler Number to Solve this Question

For those who dont know what euler no. is
E(n) for a natural number n is defined as number of numbers co-prime to n

It can be found out by following method

1) Split the required number into its prime factors
153 = 3^2 * 17

2) multiply the no. with (1-reciprocal of the prime factor)

E(n) = 153 * (1-1/3)(1-1/17) = 96

now if A^n/P where A and P are co-prime then Rem[(A^E(P))/P] = 1

here in this question as already found out above euler of 153 = 96

so since 128 and 153 are co prime => R[128^96/153] = 1

=> equation reduces to [128^(10.96).128^40]/153

=>128^40/153

now 128 = 153-25

so (-25)^40/153 => (25^40)/153

=> 625^20/153 => (612+13)^20/153 = 13^20/153 = 169^10/153 = (153+16)^10/153 = 16^10/153 = (256)^5/153 = (-50)^5/153 = (2500)^2.(-50)/153 = 52^2.(-50)/153 = 103.(-50)/153 = -50.-50/153 = 2500/153 = 52

=> this gives remainder = 52

its ans will be 0