100 followers problem-1

Let $X=\sum_{n=1}^{100} n^{100}$ . We need to find $X (\text{mod }100)$ , which amounts to finding $X (\text{mod }4)$ and $X (\text{mod }25)$ .

Euler-Fermat tells us that $a^2\equiv 1 (\text{mod }4)$ for $a$ coprime to $4$ , hence so is $a^{100}$ . If $a$ is not coprime to $4$ (i.e. even), then certainly $a^{100}\equiv 0 (\text{mod }4)$ . Hence we get $X\equiv 50\cdot 0+50\cdot 1\equiv 50 (\text{mod }4)$ .

Likewise, $a^{20}\equiv 1 (\text{mod }25)$ for $a$ coprime to $25$ , hence so is $a^{100}$ giving us $X\equiv 80\cdot 1+20\cdot 0\equiv 80 (\text{mod }25)$ .

Combining this gives us, thanks to the Chinese remainder theorem, the unique solution $X\equiv 30 (\text{mod }25)$ and $X\equiv 30 (\text{mod }4)$ , therefore $X\equiv \boxed{30} (\text{mod }100)$ .

We note that for $i,j = 0,1,2,...9$ , $(10i+j)^{100} \equiv j^{100} \pmod {100}$ .

$\begin{aligned} \sum_{k=1}^{100} {k^{100}} & \equiv 10 \sum _{k=1} ^{10} {k^{100}} \pmod{100} \end{aligned}$

Since $a=1,3,7,9$ are coprimes of $10$ , then Euler's totient theorem applies:

$\begin{aligned} \Rightarrow a^{\phi{(10)}} & \equiv 1 \pmod{10} \\ a^{4} & \equiv 1 \pmod{10} \\ \Rightarrow a^{100} & \equiv a^{4\times 25} \equiv 1 \pmod{10} \\ 5^{100} & \equiv 5 \pmod{10} \\ 2^{100} & \equiv 2^{5\times 5 \times 4} \equiv 32^{5 \times 4} \equiv 2^{5 \times 4} \equiv 2^{4} \equiv 6 \pmod{10} \\ 4^{100} & \equiv 2^{100\times 2} \equiv 6 \pmod{10} \\ 6^{100} & \equiv 2^{100}3^{100} \equiv 6 \pmod{10} \\ 8^{100} & \equiv 2^{100\times 3} \equiv 6 \pmod{10} \\ 10^{100} & \equiv 0 \pmod{10} \end{aligned}$

$\begin{aligned} \Rightarrow \sum_{k=1}^{100} {k^{100}} & \equiv 10 \sum _{k=1} ^{10} {k^{100}} \pmod{100} \\ & \equiv 10 (1+6+1+6+5+6+1+6+1 +0) \pmod{10} \\ & \equiv 330 \pmod{10} \\ & \equiv \boxed{30} \pmod{10} \end{aligned}$