Finally, it leaves some remainder

What is the remainder when 128 1000 ^{1000} is divided by 153?


Want some interesting questions like this?. Enter the world where Calculators will not help


The answer is 52.

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

Mayank Chaturvedi
Jun 15, 2016

We factorise 153 to two coprimes 153=17 X 9

128 1000 9 1000 3 2000 3 125 16 3 125 φ ( 17 ) 1 ( m o d 17 ) 128 1000 2 1000 ( 2 3 ) 333 . ( 2 ) ( 1 ) 333 . ( 2 ) 2 7 ( m o d 9 ) { 128 }^{ 1000 }\equiv { 9 }^{ 1000 }\equiv { 3 }^{ 2000 }\equiv { 3 }^{ 125*16 }\equiv { 3 }^{ 125*\varphi (17) }\equiv 1\quad (mod\quad 17)\\ { 128 }^{ 1000 }\equiv 2^{ 1000 }\equiv { ({ 2 }^{ 3 }) }^{ 333 }.(2)\quad \equiv (-1)^{ 333 }.(2)\equiv -2\equiv 7\quad (mod\quad 9)\quad

Now apply CRT to get answer

128 1000 52 m o d 153 { 128 }^{ 1000 }\equiv 52mod153

What's CRT?

alex wang - 4 years, 11 months ago

Log in to reply

Chinese remainder theorem. BTW i've added link.

Mayank Chaturvedi - 4 years, 11 months ago

Log in to reply

Oh. I didn't​ know what it stood for.

alex wang - 4 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...