29. [18] Compute the remainder when
$$
\sum_{k=1}^{30303} k^{k}
$$
is divided by 101 .
Answer: 29 The main idea is the following lemma:
Lemma. For any non-negative integer $n$ and prime $p, \sum_{k=n+1}^{n+p^{2}-p} k^{k} \equiv 1(\bmod p)$.
Proof. Note that $a^{b}$ depends only on the value of $a(\bmod p)$ and the value of $b(\bmod p-1)$. Since $p$ and $p-1$ are relatively prime, the Chinese Remainder Theorem ${ }^{4}$ implies that any $p^{2}-p$ consecutive integers will take on each possible pair of a residue $\bmod p$ and a residue $\bmod p-1$. In other words, if we let $(a, b)=(k(\bmod p), k(\bmod p-1))$, then as $k$ ranges through $p^{2}-p$ consecutive integers, $(a, b)$ will range through all $p^{2}-p$ ordered pairs of residues $\bmod p$ and residues $\bmod p-1$. This implies that
$$
\sum_{k=n+1}^{n+p^{2}-p} k^{k} \equiv \sum_{b=1}^{p-1} \sum_{a=1}^{p} a^{b} .
$$

It is well-known that $\sum_{a=1}^{p} a^{b}=\left\{\begin{array}{rr}-1 & p-1 \mid b \\ 0 & p-1 \nmid b\end{array}\right.$. We will sketch a proof here. When $p-1 \mid b$, the result follows from Fermat's Little Theorem ${ }^{5}$. When $p-1 \nmid b$, it suffices to consider the case when $b \mid p-1$, since the $b$ th powers $\bmod p$ are the same as the $\operatorname{gcd}(b, p-1)$ th powers $\bmod p$, and there are an equal number of every non-zero $b$ th power. But in this case, the $b$ th powers are just the solutions to $x^{\frac{p-1}{b}}-1$, which add up to zero by Vieta's formulas.
Now, using the formula for $\sum a^{b}$, we get that
$$
\sum_{b=1}^{p-1} \sum_{a=1}^{p} a^{b} \equiv-1 \quad(\bmod p)
$$
which completes the lemma.
We now apply the lemma with $p=101$ and $n=3,10103$, and 20103 to get that $\sum_{k=1}^{30303} k^{k} \equiv$ $\left(\sum_{k=1}^{3} k^{k}\right)-3$. But $\sum_{k=1}^{3} k^{k}=1^{1}+2^{2}+3^{3}=1+4+27=32$, so the answer is $32-3=29$.