Question

Find sum of last 4 digits of 3^3015.

Answer 1

take mod 10^4

Answer 2

can you explain how?

Answer 3

maybe use binomial thm if you're not familiar wid congruences

Answer 4

can you explain how? :p

Answer 5

\[\large 3^{3015} = 3\cdot 3^{3014} = 3(3)^{2\times 1507} =3(9)^{ 1507} = 3(10-1)^{1507}\]


expand

Answer 6

I guess it will be 1507 only?

Answer 7

I mean 1507*3

Answer 8

im getting 8907

Answer 9

\[C(1507,0)(10^{1507})({-1}^0) + C(1504,1)(10^{1506})(-1)^1+C(1504,2)(10^{1506})(-1)^2...\]

Answer 10

go from the other direction

Answer 11

\[ C(1507,0) (-1)^{1507}+ C(1507,1)({-1})^{1506}(10)+ C(1507,2)({-1})^{1505}(10)^2\]

Answer 12

and so on

Answer 13

so on until you get 10^4 term

Answer 14

you can ignore all other terms because they dont affect last four digits

Answer 15

I see..:O so it would be \[\Huge \sum_{k=1}^{k=4} C(1507,k)\]
?

Answer 16

dont forget 3
dont forget alternate signs because of -1

Answer 17

also the index must start from 0 and end at 3

Answer 18

so.....
\[\Huge \sum_{k=1}^{k=4} (-1)^kC(1507,k)\]

Answer 19

oh yeah..0 to 3..the limits

Answer 20

\[\Huge \sum_{k=0}^{k=3} (-1)^kC(1507,k)\]

Answer 21

times 3

Answer 22

yep!

Answer 23

do we have \[(-1+10)^{1507} = \sum\limits_{k=0}^{1507} \binom{1507}{k}(-1)^{1507-k}10^k\]

?

Answer 24

I got it..but I think the index should be from 0 to 4?

Answer 25

0 to 3 will do

Answer 26

10^0 ...10^1 ...10^2...10^3...10^4..till 10^4 there are 5 terms....

Answer 27

there is no harm in taking more terms.. its just useless thats all

Answer 28

there is harm

Answer 29

10^4*(stuff) is divisible by 10^4

no harm

Answer 30

do we have to take first 4 terms or till 10^4? earlier you said we gotta expand till 10^4...

Answer 31

if you do mod 10^4 at each step you are ok...but if you don't then you will have problems

Answer 32

there is subtraction in this problem

Answer 33

expand till you get 10^4

Answer 34

also the calculations are big in this expansion...without calculator its tedious..its an examination question where calculators usually aren't allowed so...

Answer 35

10^4 mod 10^4 = 0

so the term that produces 10^4 as factor is not really required

Answer 36

the moment you reach five digit number, you can ignore every thing except last four digits

Answer 37

2309480293840 = 3840

in mod 10^4

Answer 38

you can work first 3 binomial coefficients easily by hand i guess

Answer 39

I see..that makes it crystal clear :D
thanks a lot for your efforts :) @rational @Zarkon !

Answer 40

you're not even allowed shop calculator for working factorials etc ?

Answer 41

nope :|

Answer 42

oh btw, C(1507,2) = 1134771 which is itself >10^4 ?

Answer 43

then this problem should not be given in exam.. i see it is bit painful to work (1507 C 3) by hand because it is easy to make mistake while multiplying 1507*1506*1505

http://www.wolframalpha.com/input/?i=%283*%5Csum%5Climits_%7Bk%3D0%7D%5E3+%28%281507+choose+k%29%28-1%29%5E%281507-k%2910%5Ek%29%29+mod+10%5E4

Answer 44

`C(1507,2) = 1134771 which is itself >10^4 ?`


what good is this observation ?

Answer 45

you said "he moment you reach five digit number, you can ignore every thing except last four digits"

Answer 46

tell me this

what are the last four digits of number

10^4*3498573498753498574398 + 0001

?

Answer 47

4399?

Answer 48

sure ? look below :

10^4*3498573498753498574398 + 0001

34985734987534985743980000 + 0001

Answer 49

oh..I see :P

Answer 50

last four digits of

10^4*3498573498753498574398 + abcd

is abcd

Answer 51

yep.

Answer 52

it is easy to convince ourself... clearly multiplying by 10^4 shifts all the digits to left by four decimal places producing four zeroes at the end.

Answer 53

yep convinced..so..

Answer 54

look at binomial expansion

\[\begin{align}(-1+10)^{1507} &= \sum\limits_{k=0}^{1507} \binom{1507}{k}(-1)^{1507-k}10^k\\~\\&= \sum\limits_{k=0}^{3} \binom{1507}{k}(-1)^{1507-k}10^k+\color{blue}{ \sum\limits_{k=4}^{1507} \binom{1507}{k}(-1)^{1507-k}10^k}\end{align}\]

Answer 55

you can factor out 10^4 from that blue part

Answer 56

oh I see..so its not contributing..clear..:D