Question
What will be the remainder when 2 raised to the power 2003 is divided by 17?
Answers
Steve
Since 2^4 = 16, the remainder is 16, or congruent to -1.
2^8 has remainder 1
2^2003 = (2^8)^250 * 8
So, 2^2003 is congruent to 8 mod 17
Sure enough, using unix's bc program, we see that 2^2003-8 is divisible by 17:
(2^2003 - 8)/17
54029679777611977610956856526008563953991421274762127081300834674153706418464485357960446414894412702044515983011174718750452656981790839125926181466666032253708230186029308235618249010936491704201847995323993526956054335833594524210502129901395931280425880733252893557150413932058029011546430222103685967691373604227980473224649169321371321835734012470790118925509000390833886179875897078475890768619861928939010079118598484639248961016401498000725124439483337374378803662865728018428273862219590862473120200274694595542752370079732731533607188604180058906087307670975455421561395507652792871128955000.00000000000000000000000000
2^8 has remainder 1
2^2003 = (2^8)^250 * 8
So, 2^2003 is congruent to 8 mod 17
Sure enough, using unix's bc program, we see that 2^2003-8 is divisible by 17:
(2^2003 - 8)/17
54029679777611977610956856526008563953991421274762127081300834674153706418464485357960446414894412702044515983011174718750452656981790839125926181466666032253708230186029308235618249010936491704201847995323993526956054335833594524210502129901395931280425880733252893557150413932058029011546430222103685967691373604227980473224649169321371321835734012470790118925509000390833886179875897078475890768619861928939010079118598484639248961016401498000725124439483337374378803662865728018428273862219590862473120200274694595542752370079732731533607188604180058906087307670975455421561395507652792871128955000.00000000000000000000000000
ss..
so does it have a remainder of 1?
Steve
No, it has a remainder of 8