$\bmod\,10$ Prime Sum Puzzle

Wow, interesting problem! I only managed by a bit of casework - I'd be interested to know if there is a better solution.

The primes here are a bit of a distraction. The thing to focus on is that we're working $\pmod{10}$ , which means two important things when we're looking at powers $a^b$ :

• only the last digit of $a$ is important; and this can only be one of $\{1,3,7,9\}$
• only the residue of $b \pmod{4}$ is important, since $\varphi(10)=4$ and by Euler's theorem, $a^4 \equiv 1$ for all $a$ in the above set

All odd primes are congruent to either $\pm 1 \pmod{4}$ ; this depends on the last two digits of $p$ .

This drastically reduces the number of cases to check. Each decade of numbers can contain primes ending in some, none or all of the digits $\{1,3,7,9\}$ . Depending on the parity of $k$ , either those ending with $1$ and $9$ will be congruent to $1 \pmod{4}$ and those ending with $3$ and $7$ will be congruent to $-1 \pmod{4}$ , or vice-versa. This leaves a total of $2^4-1=15$ choices of the possible prime endings in the decade, and $2$ choices for the parity of $k$ , for a total of $30$ cases.

It's easy to check these cases by computer; we find that all results except $5$ are possible.