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

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?

• Use Fermat's little theorem. Oct 6, 2018 at 9:22
• Yes, the process is fine. Just try to apply Fermat's theorem and Euler's theorem to find the remaining ones. Oct 6, 2018 at 9:24
• With Fermat's Little Theorem I get that $17^{17} \equiv 17^5 \pmod{7}$, but I do not know how to proceed from there. Oct 6, 2018 at 9:25
• You still have $17 \equiv 3 \pmod{7}$ and with Fermat's little theorem $17^{17}\equiv 17^5 \equiv 3^5 \equiv 3^2 \cdot 3^2 \cdot 3 \equiv 2\cdot2\cdot3 \equiv 5 \pmod{7}$ Oct 6, 2018 at 9:31
• Multiply by $\dfrac 33$ so you have $\dfrac 13$ and the inverse of $3$ is clearly $5$. Oct 6, 2018 at 10:23

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}$$

• You have made two minor mistakes. Firstly, it is false that Fermat's little theorem gives us that anything to the power of 6 is congruent to 1. The base that is raised to the power of 6 also cannot be divisible by 7 for it to always be congruent to 1. Secondly, it should say $2^4$ rather than $2^3$ on line three in your calculation. This yields the different, and correct, answer of the the sum in question being congruent to 1 modulo 7. Oct 6, 2018 at 10:34
• For the first issue, it's only not true if $p\mid a$, which obviously isn't a problem here. You're right about the second part, it's a careless typo; I have fixed the issue. Oct 6, 2018 at 10:39

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.

• If you note the sum of bases is $15+16+17+18+19+20=105=15\times 7$. Also the sum of remainders of bases divided by 7 is $1+2+3+4+5+6=21=3\times 7$. In this case the sum is divisible by 7, that is the remainder is 0. This is a particular specification of number 7. if you add another term like $21^{21}$ or $28^{28}$, the result will be the same. Oct 6, 2018 at 11:00