Compute the remainder when 2 0 1 4 2 0 1 4 is divided by 1 0 0 0 .
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 0 1 4 2 0 1 4 ≡ 1 4 2 0 1 4 ( m o d 1 0 0 0 )
By Euler's Theorem:
( 1 4 ϕ ( 1 0 0 0 ) ) 5 = ( 1 4 4 0 0 ) 5 = 1 4 2 0 0 0 ≡ 1 5 = 1 ( m o d 1 0 0 0 )
So: 1 4 2 0 1 4 = 1 4 2 0 0 0 ⋅ 1 4 1 4 ≡ 1 4 1 4 = 2 1 4 ⋅ 7 1 4 ( m o d 1 0 0 0 )
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 1 0 0 0 :
2 1 4 = 2 1 0 ⋅ 2 4 = 1 0 2 4 ⋅ 1 6 ≡ 2 4 ⋅ 1 6 = 3 8 4 ( m o d 1 0 0 0 )
7 1 4 = 2 4 0 1 ⋅ 7 1 0 ≡ 4 0 1 ⋅ 7 ⋅ 7 9 ≡ 8 0 7 ⋅ 7 9 = ⋅ ⋅ ⋅ = 4 0 7 ⋅ 7 ≡ 8 4 9 ( m o d 1 0 0 0 )
∴ 2 0 1 4 2 0 1 4 ≡ 1 4 1 4 = 2 1 4 ⋅ 7 1 4 ≡ 3 8 4 ⋅ 8 4 9 = 3 2 6 0 1 6 ≡ 0 1 6 ( m o d 1 0 0 0 )
you are very lucky, because euler's theorem create here nothing but non sense. Euler results states that a ϕ ( n ) ≡ ( m o d n ) only when g c d ( a , n ) = 1 . I dont see here g c d ( 1 4 , 1 0 0 0 ) = 1
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 1 4 ( m o d 1 0 0 0 ) .
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.
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.
Problem Loading...
Note Loading...
Set Loading...
I'm sure there's an easier way to do this, but when in doubt, use exponentiation by squaring:
1 4 2 0 1 4 ≡ 1 9 6 1 0 0 7 ≡ 1 9 6 1 0 0 6 ( 1 9 6 ) ≡ 4 1 6 5 0 3 ( 1 9 6 ) ≡ 4 1 6 5 0 2 ( 5 3 6 ) ≡ 5 6 2 5 1 ( 5 3 6 ) ≡ 5 6 2 5 0 ( 1 6 ) ≡ 1 3 6 1 2 5 ( 1 6 ) ≡ 1 3 6 1 2 4 ( 1 7 6 ) ≡ 4 9 6 6 2 ( 1 7 6 ) ≡ 1 6 3 1 ( 1 7 6 ) ≡ 1 6 3 0 ( 8 1 6 ) ≡ 2 5 6 1 5 ( 8 1 6 ) ≡ 2 5 6 1 4 ( 8 9 6 ) ≡ 5 3 6 7 ( 8 9 6 ) ≡ 5 3 6 6 ( 2 5 6 ) ≡ 2 9 6 3 ( 2 5 6 ) ≡ 2 9 6 2 ( 7 7 6 ) ≡ 6 1 6 ( 7 7 6 ) ≡ 1 6 ( m o d 1 0 0 0 )