Find the last five digits of $1^{100}+2^{100}+3^{100}+...+999999^{100}$
Problem
Source: uzbekistan NMO 2005
Tags: modular arithmetic, number theory unsolved, number theory
04.12.2011 10:25
Here's a sketch of the method Clearly it suffices to find the sum modulo $2^5$ and $5^5$. Now you know that cool lemma that $\sum_{i=1}^{p-1} i^k \equiv 0 \pmod{p}$ if $p \nmid k$? Well, it generalizes to any power $p^m$ due to the fact the units in $\mathbb{Z}_{p^n}$ have a primitive root. Thus I'm pretty sure the last five digits must be $00000$ unless I messed up something big.
04.12.2011 10:37
How I prove the lemma
08.12.2011 09:45
shohvanilu wrote: Find the last five digits of $1^{100}+2^{100}+3^{100}+...+999999^{100}$ It is easy $LHS=1^{100}+999999^{100}+2^{100}+999998^{100}.....500000^{100}=1000000A+1000000B+...+1000000M+500000N=500000(2A+2B+...+2M+N)=.....00000$
08.12.2011 09:48
SORRY SORRY $LHS=1^{100}+2^{100}+...+(1000000-1)^{100}=1^{100}+1000000N-1^{100}+...=...00000$
14.11.2015 11:05
Uzbekistan wrote: SORRY SORRY $LHS=1^{100}+2^{100}+...+(1000000-1)^{100}=1^{100}+1000000N-1^{100}+...=...00000$ It's wrong. Since $100$ is even, hence $(1000000-1)^{100}=1000000N+1^{100}$