Can you solve it without using CRT?

Level pending

What is the remainder when 2 999 2^{999} is divided by 100 100 .This problem isn't original.

22 88 44 66

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Adarsh Kumar
Mar 20, 2015

I know,I know this problem can be easily killed using Chinese Remainder Theorem but I don't know this theorem and hence solved it in this way: First of all,let us say that, 2 999 = 100 x + a 2^{999}=100*x+a .Now,let us divide the equation by 2 2 2^2 ,it becomes, 2 997 = 25 x + a 4 2^{997}=25x+\dfrac{a}{4} .Now,if we find the remainder when 2 997 2^{997} is divided by 25 25 we would get a 4 \dfrac{a}{4} and thus, a a .For finding that consider this: 2 5 7 ( m o d 25 ) 2 10 49 ( 1 ) ( m o d 25 ) 2 990 ( 1 ) 24 ( m o d 25 ) 2 997 ( 24 128 ) 3072 22 ( m o d 25 ) 2^5\equiv 7\pmod{25}\\ \Rightarrow 2^{10}\equiv 49\equiv(-1)\pmod{25}\\ \Rightarrow 2^{990}\equiv (-1)\equiv 24\pmod{25}\\ \Rightarrow 2^{997}\equiv (24*128)\equiv 3072\equiv 22\pmod{25} .That implies a 4 = 22 a = 22 4 = 88 \dfrac{a}{4}=22\Rightarrow a=22*4=88 .

@Nihar Mahajan how did you solve it?

Adarsh Kumar - 6 years, 2 months ago

Well, this solution also uses modular arithmetic. You should consider changing the title of the problem.

Prasun Biswas - 6 years, 2 months ago

Log in to reply

Yes but it does not use CRT which uses nothing but modular arithmetic.How about this'Can you solve it without mod?'?

Adarsh Kumar - 6 years, 2 months ago

Log in to reply

Better would be "Can you solve it without CRT?" since mod again refers to modular arithmetic which is used heavily in your solution.

Prasun Biswas - 6 years, 2 months ago

Log in to reply

@Prasun Biswas ok! thanx!

Adarsh Kumar - 6 years, 2 months ago

Log in to reply

@Adarsh Kumar BTW how did u solve it?

Adarsh Kumar - 6 years, 2 months ago

Log in to reply

@Adarsh Kumar Yes. Using modular arithmetic, of course. :D

I think that a solution using binomial coefficients might be possible but I'm not quite sure about that.

Prasun Biswas - 6 years, 2 months ago

Log in to reply

@Prasun Biswas No,I mean did u use my method or CRT?

Adarsh Kumar - 6 years, 2 months ago

Log in to reply

@Adarsh Kumar Nope, I used CRT.

Prasun Biswas - 6 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...