2014^2014

Level pending

Compute the remainder when 201 4 2014 2014^{2014} is divided by 1000 1000 .


The answer is 16.

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.

3 solutions

Cody Johnson
Jan 1, 2014

I'm sure there's an easier way to do this, but when in doubt, use exponentiation by squaring:

1 4 2014 19 6 1007 19 6 1006 ( 196 ) 41 6 503 ( 196 ) 41 6 502 ( 536 ) 5 6 251 ( 536 ) 5 6 250 ( 16 ) 13 6 125 ( 16 ) 13 6 124 ( 176 ) 49 6 62 ( 176 ) 1 6 31 ( 176 ) 1 6 30 ( 816 ) 25 6 15 ( 816 ) 25 6 14 ( 896 ) 53 6 7 ( 896 ) 53 6 6 ( 256 ) 29 6 3 ( 256 ) 29 6 2 ( 776 ) 616 ( 776 ) 16 ( m o d 1000 ) \begin{aligned} 14^{2014}&\equiv196^{1007}\\&\equiv196^{1006}(196)\\&\equiv416^{503}(196)\\&\equiv416^{502}(536)\\&\equiv56^{251}(536)\\&\equiv56^{250}(16)\\&\equiv136^{125}(16)\\&\equiv136^{124}(176)\\&\equiv496^{62}(176)\\&\equiv16^{31}(176)\\&\equiv16^{30}(816)\\&\equiv256^{15}(816)\\&\equiv256^{14}(896)\\&\equiv536^7(896)\\&\equiv536^6(256)\\&\equiv296^3(256)\\&\equiv296^2(776)\\&\equiv616(776)\\&\equiv\boxed{16}\pmod{1000} \end{aligned}

Jubayer Nirjhor
Jan 1, 2014

201 4 2014 1 4 2014 ( m o d 1000 ) 2014^{2014}\equiv 14^{2014}\pmod{1000}

By Euler's Theorem:

( 1 4 ϕ ( 1000 ) ) 5 = ( 1 4 400 ) 5 = 1 4 2000 1 5 = 1 ( m o d 1000 ) \left(14^{\phi(1000)}\right)^5=\left(14^{400}\right)^5=14^{2000}\equiv 1^5=1 \pmod{1000}

So: 1 4 2014 = 1 4 2000 1 4 14 1 4 14 = 2 14 7 14 ( m o d 1000 ) 14^{2014}= 14^{2000}\cdot 14^{14}\equiv 14^{14} =2^{14}\cdot 7^{14}\pmod{1000}

I don't know a short-cut for the rest calculation. However, if one doesn't want to touch calculator, then he can work out the rest step by step multiplying and then taking modulo 1000 1000 :

2 14 = 2 10 2 4 = 1024 16 24 16 = 384 ( m o d 1000 ) 2^{14}=2^{10}\cdot 2^4=1024\cdot 16\equiv 24\cdot 16 =384 \pmod{1000}

7 14 = 2401 7 10 401 7 7 9 807 7 9 = = 407 7 849 ( m o d 1000 ) 7^{14}=2401\cdot 7^{10}\equiv 401\cdot 7 \cdot 7^9\equiv 807\cdot 7^9=\cdot\cdot\cdot=407\cdot 7\equiv 849 \pmod{1000}

201 4 2014 1 4 14 = 2 14 7 14 384 849 = 326016 016 ( m o d 1000 ) \therefore ~~~ 2014^{2014}\equiv 14^{14}=2^{14}\cdot 7^{14}\equiv 384\cdot 849 = 326016\equiv \fbox{016}\pmod{1000}

you are very lucky, because euler's theorem create here nothing but non sense. Euler results states that a ϕ ( n ) ( m o d n ) a^{\phi(n)}\equiv \pmod n only when g c d ( a , n ) = 1 gcd(a,n)=1 . I dont see here g c d ( 14 , 1000 ) = 1 gcd(14,1000)=1

Sayan Das - 7 years, 5 months ago

I like your use of Euler's Theorem, it saved a lot of computation. At that point, I'd use my method above (or below) to compute 1 4 14 ( m o d 1000 ) 14^{14}\pmod{1000} .

Cody Johnson - 7 years, 5 months ago

Log in to reply

But (14,2000) is equal to 2,not 1, so you can't use it directly.You can use that EVERY even number on the power of 100 gives remainder 376 when divided by 1000.

Bogdan Simeonov - 7 years, 5 months ago

Okay, I solved this problem in a real lengthy method. I'm sure there may be an easier approach, so if any of you guys get to know any shorter method which will save a lot of time, do tell me. The remainder when 2014^2014 is divided by 1000 is actually the last three digits of the number 2014^2014. So using modulo function, we'll see that 2014^2000 will leave a remainder 376 when divided by 1000. Moreover, 2014^14 will leave a remainder 16 when divided by 1000. So the remainder left by 2014^2014 when divided by 1000 will be 16. Actually the last three digits are 016, but we neglect 0 here because they have asked for the remainder.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...