Remainder Problem

sathyaprakashg · Joined: 13 Oct 2005 Posts: 1 Location: Kurukshetra

What is the remainder when (128)^500 is divided by 153.

nirav_21 · Joined: 10 Oct 2005 Posts: 5 Location: Bhavnagar,Gujarat

128^500 by 153
hi dear,
i hope u might have got acquainted with the remainder theorm method by now, and if not here is the description for this particular question.

128^500, just try to divide 128 by 153, the remainder is 128 a very big no, u have to make this number smaller and smaller.
now think of 128^2 = 16384, which on division by 153 gives, 13 as the remainder.
so we can write
128^500 = ((128)^2)^250
= (13)^250 (remainder on division by 153)
= (169)^125
= (16)^125 (remainder on division by 153)
= ((16)^5)^3
= (52)^3 (remainder on dividing 16^5 = 65536 by 153 is 52)
= 140608
= 1 (Dividing 140608 by 153 leaves the remainder 1)
See dear this is a very easy method if u adopt but this sum is very lengthy and involves more multiplication, but by practice u will get used to this method.
Cheers.
If satisfied with the answer please do respond.
bye'

palagg · Joined: 22 Feb 2006 Posts: 12

hiii

there is a method to solve such ques... 1 reply u already got and my method is also similar to dat

c 128^500/153

first v take 128^1/153 and remainder is 128
dn 128^2/153= remainder of 128^1/153 * remainder of 128^1/153
ie 128*128/153=13
next similarly 128^3/153= 13*128/153
do this and there vil b many cycles and cycle ends wen remainder is 1 or it repeats.. dn u can take divide the power with dat no. and get the result.. it is nt always dat v get so many cycles. there r very few ques where v get so many cycles. try this. once u get used to it vil b very helpful
biii