Show that $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{63}$

Question

Show that $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{63}$
According to Fermat's theorem:
$$1^7+7^7+13^7+19^7+23^7\equiv{1+7+13+19+23}\pmod{7}\equiv{63}\pmod{7}\equiv{0}\pmod{7}$$
Now we need to show: $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{9}$ , but how??

Answer 1

Since OP demands a proof without Euler's theorem, below is one:
First we denote the sum as $S$ and modulo $9:$
$$S\equiv1^7+(-2)^7+4^7+1^7+5^7\pmod9.$$
Since $(-2)^3\equiv1\pmod9,$ we find that $(-2)^7\equiv-2\pmod9,$ so that $$S\equiv4^7+5^7\pmod9.$$
But $5\equiv-4\pmod9,$ so $$S\equiv4^7+(-4)^7\equiv0\pmod9.$$

Hope this helps.

Answer 2

Just as Fermat's theorem tells you that $x^6\equiv1\pmod{7}$, Euler's theorem (which generalizes Fermat's) tells you that $x^6\equiv1\pmod{9}$ whenever $\gcd(x,9)=1$. It follows that $$1^7+7^7+13^7+19^7+23^7\equiv1+7+13+19+23\equiv0\pmod{9}.$$

Answer 3

Just to be a bit different, note that a binomial expansion tells us

$$7^7=(1+6)^7=1+7\cdot6+(\text{stuff})\cdot6^2\equiv43\equiv-2\mod 9$$

since $6^2\equiv0$ mod $9$, and thus, since $13\equiv4$, $19\equiv1$, and $23\equiv-4$ mod $9$, we have

$$1^7+7^7+13^7+19^7+23^7\equiv1^7-2+4^7+1^7+(-4)^7=1-2+4^7+1-4^7=0\mod 9$$