What is $15^{15} + 16^{16} + 17^{17} + 18^{18} + 19^{19} + 20^{20} \pmod{7}$?

Question

I am trying to evaluate $15^{15} + 16^{16} + 17^{17} + 18^{18} + 19^{19} + 20^{20} \pmod{7}$. I have found that $15^{15} \equiv 1 \pmod{7}$ and that $16^{16} \equiv 2 \pmod{7}$.

To evaluate $15^{15} \pmod{17}$, I did the following: $$15 = 2 \times 7 + 1 \equiv 1 \pmod{7}$$ $$15^{15} \equiv 1 \pmod{7}$$

Then, to evaluate $16^{16}$, I wrote: $$16 = 15 + 1 \equiv 1 + 1 = 2 \pmod{7}$$ $$16^{16} \equiv 2^{16} \pmod{7}$$

$$2^{3} = 8 = 7+1 \equiv 1 \pmod{7}$$ $$2^{16} = 2^{3} \times 2^{13} \equiv 2^{13} = 2^{3} \times 2^{10} \equiv 2^{10} \equiv \dots \equiv 2 \pmod{7}$$

Nevertheless, I have not managed to figure out how to evaluate $17^{17}$. How should I go about this and is my overall approach for evaluating the sum in question a good one?

Answer 1

Euler's Theorem states that $$ a^{\phi(n)}\equiv1 \pmod{n}$$ For all $n$, where $\phi(n)$ is the Euler totient function, denoting the number of positive integers less than $n$ relatively prime to $n$. For primes, $\phi(n)=n-1$. Thus $$ a^{n-1}\equiv1\pmod n. $$ This result is also known as Fermat's little theorem. Now, $7$ is prime, so anything to the power of $6$ is congruent to $1$. We have $$\begin{split} &15^{15}+16^{16}+17^{17}+18^{18}+19^{19}+20^{20}\\ \equiv\, & 15^3 + 16^4 + 17^5 + 18^0 + 19^1 + 20^2 \\ \equiv \, & 1^3 + 2^4 + 3^5 + 4^0 + 5^1 + 6^2\\ \equiv\, & 1+16+243+1+5+36\\ \equiv\, & 302\\ \equiv\, & 1\pmod{7}. \end{split}$$

Answer 2

You can go with the same process I think:

$$17^{17} \equiv 3^{17} \mod{7}$$

and we have

$$3^1 \equiv 3 \mod{7}$$ $$3^2 \equiv 2 \mod{7}$$ $$3^3 \equiv 6 \mod{7}$$ $$3^4 \equiv 4 \mod{7}$$ $$3^5 \equiv 5 \mod{7}$$ $$3^6 \equiv 1 \mod{7} \text{ (We could have this by using Fermat's Little Theorem as well)}$$

From here, we can conclude that $3^{17} \equiv 5 \mod{7}$.

Then, notice that

$$18 \equiv 4 \equiv -3 \mod{7}$$ $$19 \equiv 5 \equiv -2 \mod{7}$$ $$20 \equiv 6 \equiv -1 \mod{7}$$ which means you can find other terms by using your previous results for $15,16$ and $17$.

But as suggested on comments, a better way is to use Fermat's Little Theorem.