what is the remainder when 2^2003 is divided by 17? the question is from binomial theorem. Answer is 8.?

Question

preferrably do it by binomial theorem....n plz explain me clearly how to do it. if it involves too much of calculation, then plz indicate the steps in words.
THANK U, any help will be appreciated.

Answer 1

we can solve it using modular arithmetic(others have done with binomial theorem)

2^4 = 16 = -1 mod 17

so (2^4)^500 = (-1)^500 mod 17
= 1 mod 17

so 2^2000 = 1 mod 17

so 2*2003 = 1*2^3 mod 17 = 8 mod 17

so remainder = 8 when devided by 17

Answer 2

Fascinating, Captain. I think that the answer is indeed : 8 (!) (NOT factorial "!" but exultatory "!")

17 is 2^4 + 1 = 2^4 (1 + 1/2^4)

So: the binomial theorem gives us, among other things, that

1/[1 + x] = [1 + x]^(-1) = 1 - x + x^2 - x^3 + x^4 -... provided mod x < 1.

So, 2^2003 / [2^4 (1 + 1/2^4)] = 2^1999 [1 + 1/2^4]^(-1) =

2^1999 (1 - 1/2^4 + 1/2^8 - ... - 1/2^1996 + 1/2^2000 -1/2^2004 ...

(Powers that are odd multiples of 4 have a -ve sign, even multiples a +ve sign.)

The last whole number coming out of this thing is 2^1999/2^1996 = 2^3 = 8. Any of the rest is the "remainder" DIVIDED by 17; so to get the remainder, we must multiply what appears after the 1/2^1996 term by 17.

What is left over, then, is 17 2^1999 (1/2^2000)(1 - 1/2^4 + 1/2^8 - ...

or 17 (1/2) [1 + 1/2^4]^(-1), using the binomial theorem again.

But [1 + 1/2^4] = I/2^4 [2^4 + 1] = 17 / 16.

So the remainder is, finally, 17 (1/2) 16 / 17 = 8 (! Glory be.)

PHEW --- that was a GREAT question --- THANK YOU.

Live long and prosper.

Answer 3

Interesting question. I don't see anything obvious. We know that

2^2003 = sum k=o to 2003 { 2003Ck }

Where the binomial coefficients can be described in terms of Pascal's triangle.

Let's see 2^2003 mod 17 = 2^3 -> (2^2003-8 mod 17 = 0, or

2^2003-8 is divisible by 17. factor out 2^3:

2^3(2^2000-1) divisible by 17

(2^1000+1)(2^1000-1) is divisible by 17

keep factoring those differences between 2 squares

1000/2 = 500
500/2 = 250
250/2 = 125

you'd eventually get a factor:
2^125+1

what i'm trying to do is get something like 2^4+1 because that is equal to 17.

Maybe I should have factored out 4 rather than 8 early on:
4(2^2001-2) divisible by 17
No, how about multiplying by 2:
2^2004-16 divisible by 17
now factor
(2^1002+4)(2^1002-4) divisible by 17
(2^501+2)(2^501-2) div by 17
now factor out a 2 and factor still no help!

Answer 4

It does not supply a diverse answer! a million) (3x + 2)^8 = 3x^8 + 48x^7 + 336x^6 + 1344x^5 + 3360x^4 + 5376x^3 + 5376x^2 + 3072x + 768 2) (2 + 3x) ^8 = 3x^8 + 48x^7 + 336x^6 + 1344x^5 + 3360x^4 + 5376x^3 + 5376x^2 + 3072x + 768

Answer 5

Wal C's answer is elegant and easily understood. Except that 2^2000 = (2^4)^500, not (2^4)^50. Minor issue, since the solution is basically correct.

Answer 6

2^2003 = (2^4)^50 *2^3

= 8*(17 - 1)^50

= 8*(17^50 - 50C1* 17^49 + 50C2*17^48 + ... -50C49*17 + 1)

So 2^2003/17

= 8*(17^50 - 50C1* 17^49 + 50C2*17^48 + ... -50C49*17 + 1)/17

= 8*(17^50 - 50C1* 17^49 + 50C2*17^48 + ... -50C49*17)/17 + 8/17

So the remainder = 8 as all the other terms have 17 as a factor