Remainder of a Huge Number

Algebra Level 3

1 1 2 2 6 6 4 4

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.

4 solutions

Rafael Ticzon
Mar 31, 2014

We are given of the following number: 2 1000 + 2 1001 + 2 1002 + 2 1003 { 2 }^{ 1000 } + { 2 }^{ 1001 } + { 2 }^{ 1002 } + { 2 }^{ 1003 }

Factoring that number, we get: 2 1000 ( 2 0 + 2 1 + 2 2 + 2 3 ) 2 1000 ( 1 + 2 + 4 + 8 ) 2 1000 ( 15 ) { 2 }^{ 1000 }({ 2 }^{ 0 }+ { 2 }^{ 1 } +{ 2 }^{ 2 }+ { 2 }^{ 3 })\Rightarrow { 2 }^{ 1000 }(1+2+4+8)\Rightarrow { 2 }^{ 1000 }(15)

That number is also equivalent to: 2 1000 ( 14 + 1 ) 2 1000 ( 14 ) + 2 1000 { 2 }^{ 1000 }(14+1)\Rightarrow { 2 }^{ 1000 }(14)+{ 2 }^{ 1000 }

Dividing the number by 7, it's quotient will be expressed as: [ 2 1000 ( 14 ) + 2 1000 ] / ( 7 ) { [2 }^{ 1000 }(14)+{ 2 }^{ 1000 }]/(7)

[ 2 1000 ( 14 ) / 7 ] + ( 2 1000 / 7 ) \Rightarrow \quad [{ 2 }^{ 1000 }(14)/7]+({ 2 }^{ 1000 }/7)

Upon observation, you would see that the first term is already divisible by 7 (from dividing 14 by 7); thus, we can only get the remainder from the second term.

Organizing a table with the powers of 2 and the corresponding remainder when divided by 7, we obtain a pattern: 2 1 2 2 2 4 2 3 1 2 4 2 2 5 4 2 6 1 . . . { 2 }^{ 1 }\rightarrow 2\\ { 2 }^{ 2 }\rightarrow 4\\ { 2 }^{ 3 }\rightarrow 1\\ { 2 }^{ 4 }\rightarrow 2\\ { 2 }^{ 5 }\rightarrow 4\\ { 2 }^{ 6 }\rightarrow 1\\ \quad...

wherein, for every set of 3 numbers, the remainders keep on repeating.

Notice that 3 and 6 are divisible by 3, and both have the same remainder. Since 999 is also divisible by 3, the remainder [i.e. 1] of 2 999 { 2 }^{ 999 } will also be the same when divided by 7. Following that, the table is extended to: . . . 2 999 1 2 1000 2 \quad ...\\ { 2 }^{ 999 }\rightarrow 1\\ { 2 }^{ 1000 }\rightarrow 2

Hence, the remainder of the number upon division by 7 is 2 \boxed{2}

Saurabh Mallik
Jun 14, 2014

We can solve this question using m o d mod function.

2 1000 + 2 1001 + 2 1002 + 2 1003 2^{1000}+2^{1001}+2^{1002}+2^{1003} m o d mod 7 7

2 1000 ( 2 0 + 2 1 + 2 2 + 2 3 ) 2^{1000}(2^{0}+2^{1}+2^{2}+2^{3}) m o d mod 7 7

2 1000 ( 1 + 2 + 4 + 8 ) 2^{1000}(1+2+4+8) m o d mod 7 7

2 1000 × 15 2^{1000}\times15 m o d mod 7 = 2 7=2

Thus, the answer is: 2 1000 × 15 2^{1000}\times15 m o d mod 7 = 2 7=\boxed{2}

exp. = 2^{1000} (1 + 2 + 4 +8) = 2^{1000} 15 = 2^{1000} (14 + 1)
Since 2^{1000}
14 is divisible by 7, we need to test only 2^{1000}
2^{1000} ={ ( 2^10)^10 }^10
( 2^10)/7 gives remainder as 2 , repeating twice gives 2. This is only another method.
How ever the method Rafael Ticzon has given for the pattern of power of 2 is really better.
Hats off young Rafael Ticzon.


Sudha Parimala
Mar 21, 2014

{ 2 }^{ 3 }\quad =\quad 1(mod\quad 7)\ { 2 }^{ 999 }\quad =\quad 1(mod\quad 7)\ { 2 }^{ 1000 }=\quad 2(mod\quad 7)\ { 2 }^{ 1001 }\quad =\quad 2\times 2(mod\quad 7)\quad =\quad 4(mod\quad 7)\ { 2 }^{ 1002 }\quad =\quad 8(mod\quad 7)\quad =\quad 1(mod\quad 7)\ { 2 }^{ 1003 }\quad =\quad 2(mod\quad 7)\ total\quad =\quad 2+4+1+2=9\ 9\quad =\quad 2(mod\quad 7) so the answer is 2.

LaTeX didn't work.... You should've previewed it before posting....

Satvik Golechha - 7 years, 2 months ago

2 3 = 1 ( m o d 7 ) { 2 }^{ 3 }\quad =\quad 1(mod\quad 7) 2 999 = 1 ( m o d 7 ) { 2 }^{ 999 }\quad =\quad 1(mod\quad 7) 2 1000 = 2 ( m o d 7 ) 2 1001 = 2 × 2 ( m o d 7 ) = 4 ( m o d 7 ) 2 1002 = 8 ( m o d 7 ) = 1 ( m o d 7 ) 2 1003 = 2 ( m o d 7 ) t o t a l = 2 + 4 + 1 + 2 = 9 9 = 2 ( m o d 7 ) { 2 }^{ 1000 }=\quad 2(mod\quad 7)\ { 2 }^{ 1001 }\quad =\quad 2\times 2(mod\quad 7)\quad =\quad 4(mod\quad 7)\ { 2 }^{ 1002 }\quad =\quad 8(mod\quad 7)\quad =\quad 1(mod\quad 7)\ { 2 }^{ 1003 }\quad =\quad 2(mod\quad 7)\ total\quad =\quad 2+4+1+2=9\ 9\quad =\quad 2(mod\quad 7) so the answer is 2.

Datu Oen - 7 years, 2 months ago

Log in to reply

I have a solution : After having reduced to the term to (14 + 1) 2^1000 = 14 2^1000 +2^1000 So we have remainder only in 2^1000(First part is multiple of 14) 2^1000 = 8 * 2^997 = (7 + 1) * 2^997 = 7 2^996 + 2^997 So we will have remainder only in 2^997.

2^997 = 2* (2)^996 = 2* ( 2^8)^126 = 2* ( 63 + 1)^126 = 2* ( 126 C 0 * 63^126 + 126 C 1 * 63^ 125 +..................+ 126 C 125 * 63 + 1) = 2* ( ........................................................ " ...............................................................) + 2 As the terms in brackets are multiples of 63( i.e. 7), clearly remainder is 2

Rajendra MISRA - 7 years, 1 month ago

Log in to reply

Thanks. Sorry for the "solution" I posted. It was an attempt to make the previous solution in latex form but it did not come up as expected.

Datu Oen - 7 years, 1 month ago

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...