I am stuck on this modular arithmetic problem for homework practice: $$\sum_{k=1}^{300} k^k \pmod 7$$
I am not quite sure how to approach this problem. I've tried finding a pattern between the sums but i do not think there is one. I know how to find mods of a^b (mod c) but for this question i am clueless. Any hints and help appreciated.
For any $k$ there are integers $q,r$ such that $k=7q+r$ where $0\leq r\leq 6$.
So $$k^k=(7q+r)^{(7q+r)}\cong r^{(7q+r)}\quad (mod 7).$$
From you should use Fermat little theorem.
Can you take it from here?
It does repeat, but only after $7*6 = 42$ terms (the bases repeat in cycles of 7 while the exponents repeat in cycles of 6). Try breaking it up like this $$\sum_{k=1}^{43} 1^{1 + 7(k-1)} + \sum_{k=1}^{43} 2^{2+7(k-1)} + \sum_{k=1}^{43} 3^{3+7(k-1)} + \sum_{k=1}^{43} 4^{4+7(k-1)} + \sum_{k=1}^{43} 5^{5+7(k-1)} + \sum_{k=1}^{43} 6^{6+7(k-1)} + \sum_{k=1}^{42} 7^{7+7(k-1)}$$ Now, the exponents can be reduced $\bmod{6}$, since $a^{6} \equiv 1 \bmod{7}$ for every $a \neq 0$. This gives $$\sum_{k=1}^{43} \left( 1^{1 + (k-1)} + 2^{2+(k-1)} + 3^{3+(k-1)} + 4^{4+(k-1)} + 5^{5+(k-1)} + 6^{(k-1)}\right)$$ or equivalently $$7\sum_{k=1}^{6} \left(1^{1 + (k-1)} + 2^{2+(k-1)} + 3^{3+(k-1)} + 4^{4+(k-1)} + 5^{5+(k-1)} + 6^{(k-1)}\right) + 1^{1} + 2^{2} + 3^{3} + 4^{4} + 5^{5} + 6^{0}$$
To summarize what is below, basically $(x+42)^{x+42}\equiv x^x\pmod{7}$ and since $300=42\times7+6$ there are $7$ periods of same remainders plus 6 extra things so the remainder has to equal to the 6 extra things.
For writing convinience we denote $0^0=0$ in this anwer.
Now apply fermat little theorem $x^6\equiv1\pmod{7}$ we get your sum is congruent to
$$0^0+1^1+2^2+...+6^0+7^1+8^2+...+12^0+13^1+...299^5+300^0$$
which is congruent to
$$0^0+1^1+2^2+...+6^0+0^1+1^2+...+5^0+6^1+...5^5+6^0$$
We group each seven together:
$$(0^0+1^1+2^2+...+6^0)+(0^1+1^2+...+5^0+6^1)+...+(0^5+...+6^5)+...+(0^0+...+5^5+6^0)$$
Now every period consists of $6$ groups.
Now each "6-groups" have 42 elements and $300=42\cdot7+6$ so there are $7$ "6-group"s and your sum is congrent to $(0^0+1^1+2^2+3^3+4^4+5^5+6^0)\equiv 5\pmod{7}$
