A number theory problem by K. J. W.

Let X = 9 1 + 9 2 + . . . + 9 244 { 9 }^{ 1 }+{ 9 }^{ 2 }+...+{ 9 }^{ 244 }

Find the remainder when X is divided by 1000.


The answer is 180.

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.

2 solutions

K. J. W.
Jul 11, 2014

N o t e t h a t 9 n + 9 n + 1 = 9 n ( 9 + 1 ) = 10 ( 9 n ) T h e r e f o r e 9 1 + 9 2 + . . . + 9 244 = 10 ( 9 1 + 9 3 + . . . + 9 243 ) S o w e o n l y n e e d t o n o t e t h e l a s t t w o d i g i t s o f e a c h o f 9 1 , 9 3 , . . . , 9 243 s i n c e t h e y w i l l b e c o m e t h e t h i r d a n d s e c o n d l a s t d i g i t s o f X a n d t h e l a s t d i g i t o f X w i l l b e 0. A l s o n o t e t h a t 9 ( m o d 100 ) × 81 29 ( m o d 100 ) 29 ( m o d 100 ) × 81 49 ( m o d 100 ) 49 ( m o d 100 ) × 81 69 ( m o d 100 ) 69 ( m o d 100 ) × 81 89 ( m o d 100 ) 89 ( m o d 100 ) × 81 9 ( m o d 100 ) T h e r e f o r e 9 1 + 9 3 + . . . + 9 243 ( m o d 100 ) 24 ( 9 + 29 + 49 + 69 + 89 ) + 9 + 29 ( m o d 100 ) 5880 + 38 ( m o d 100 ) 5918 ( m o d 100 ) 18 ( m o d 100 ) S o t h e l a s t 3 d i g i t s o f X a r e 18 × 10 = 180 Note\quad that\\ \\ { 9 }^{ n }+{ 9 }^{ n+1 }\\ ={ 9 }^{ n }(9+1)\\ =10({ 9 }^{ n })\\ \\ Therefore\\ \\ { 9 }^{ 1 }+{ 9 }^{ 2 }+...+{ 9 }^{ 244 }\\ \\ =10({ 9 }^{ 1 }+{ 9 }^{ 3 }+...+{ 9 }^{ 243 })\\ \\ So\quad we\quad only\quad need\quad to\quad note\quad the\quad last\quad two\quad digits\quad of\quad each\quad of\quad { 9 }^{ 1 },{ 9 }^{ 3 },...,{ 9 }^{ 243 }\\ \\ since\quad they\quad will\quad become\quad the\quad third\quad and\quad second\quad last\quad digits\quad of\quad X\quad and\quad the\quad last\quad digit\quad of\quad X\quad will\quad be\quad 0.\\ \\ Also\quad note\quad that\\ \\ 9(mod\quad 100)\times 81\quad \equiv \quad 29(mod\quad 100)\\ 29(mod\quad 100)\times 81\quad \equiv \quad 49(mod\quad 100)\\ 49(mod\quad 100)\times 81\quad \equiv \quad 69(mod\quad 100)\\ 69(mod\quad 100)\times 81\quad \equiv \quad 89(mod\quad 100)\\ 89(mod\quad 100)\times 81\quad \equiv \quad 9(mod\quad 100)\\ \\ Therefore\quad { 9 }^{ 1 }+{ 9 }^{ 3 }+...+{ 9 }^{ 243 }(mod\quad 100)\\ \equiv \quad 24(9+29+49+69+89)+9+29(mod\quad 100)\\ \equiv \quad 5880+38(mod\quad 100)\\ \equiv \quad 5918(mod\quad 100)\\ \equiv \quad 18(mod\quad 100)\\ \\ So\quad the\quad last\quad 3\quad digits\quad of\quad X\quad are\quad 18\times 10=\boxed { 180 }

Kartik Sharma
Aug 2, 2014

@K. J. W. Nice problem!!!!

X = 9 1 + 9 2 + 9 3 . . . . + 9 244 {9} ^ {1} + {9} ^ {2} + {9} ^ {3}.... + {9}^{244}

Then, X = 9 ( 9 244 1 ) 9 1 \frac { 9({ 9 }^{ 244 }-1) }{ 9-1 }

Therefore, we have to find

9 ( 9 244 1 ) 8 \frac { 9({ 9 }^{ 244 }-1) }{ 8 } mod\quad 9

So, we have to find 9 244 { 9 }^{ 244 } mod\quad 9

From Euler's theorem,

9 φ ( 1000 ) {9}^{\varphi(1000)} = 1 mod 1000

9 400 {9}^{400} = 1 mod 1000

9 200 {9}^{200} = 1 mod 1000

Now, 9 44 {9}^{44} can be found easily and so,

9 244 {9}^{244} = 161 mod 1000

Putting this value in above equation, we get

\(\frac { 9(160) }{ 8 } ) = 9 * 20 = 180

Ask me here if you are not able to understand how to find 9^44!!

Kartik Sharma - 6 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...