Challenge for champions !!! 2

Given that x 100 a ( m o d 1000 ) x^{100} \equiv a (mod 1000) , x Z + x\in \mathbb Z^{+} , x < 98 x<98 find sum of all possible values of a a and 0 a 999 0\leq a\leq999 .


Try more problems from set Challenges for champions!!!


The answer is 1002.

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

Let m m be a natural number and r r be the last digit of m m .


Then m r ( m o d 10 ) m 10 r 10 m o d ( 1 0 2 ) m \equiv r (mod 10) \implies m^{10} \equiv r^{10} mod(10^{2})

( m 10 ) 10 ( r 10 ) 10 m o d ( 1 0 3 ) \implies (m^{10})^{10} \equiv (r^{10})^{10} mod (10^{3})

i.e. m 100 r 100 ( m o d 1000 ) m^{100} \equiv r^{100} (mod 1000)


Case 1:- \textbf{Case 1:-}

If r = 0 r = 0 , r 100 0 ( m o d 1000 ) r^{100} \equiv 0 (mod 1000) . So last three digits are 000 000


Case 2:- \textbf{Case 2:-}

If r = 1 , 3 , 7 , 9 r=1,3,7,9 , then r 2 1 ( m o d 8 ) r^{2} \equiv 1 (mod 8) , so r 100 1 ( m o d 8 ) r^{100} \equiv 1 (mod 8) , Also ( 125 ) = 100 \emptyset (125) = 100 By Euler's Theorem, as ( r , 5 ) = 1 , r 100 1 ( m o d 125 ) (r,5)=1, r^{100} \equiv 1 (mod 125) . Hence, r 100 1 ( m o d 1000 ) r^{100} \equiv 1(mod 1000) . So last 3 digits are 001 001


Case 3:- \textbf{Case 3:-}

If r = 5 r=5 then r 2 1 ( m o d 8 ) r^{2} \equiv 1 (mod 8) . Hence r 100 1 ( m o d 8 ) r^{100} \equiv 1(mod 8) and r 100 0 ( m o d 125 ) r^{100} \equiv 0 (mod 125) . Using Chinese remainder theorem, r 100 625 ( m o d 1000 ) r^{100} \equiv 625 (mod 1000) . So last 3 digits are 625 625


Case 4:- \textbf{Case 4:-}

If r = 2 , 4 , 6 , 8 r = 2,4,6,8 then r 100 0 ( m o d 8 ) r^{100} \equiv 0 (mod 8) . Since ( r , 5 ) = 1 (r,5)=1 we get r 100 1 ( m o d 125 ) r^{100} \equiv 1 (mod 125) . By Chinese remainder theorem, r 100 376 ( m o d 1000 ) r^{100} \equiv 376 (mod 1000) . So last 3 digits are 376 376


Adding all the above numbers we get addition as 1002 \boxed {1002}

Can you explain how you used the condition that x < 98 x < 98 , or why it's necessary?

Calvin Lin Staff - 6 years, 2 months ago

@Ramprasad Rakhonde Can you help me out with the first step?

Ankit Kumar Jain - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...