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

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??

• Do you know of Euler's theorem? It expands Fermat's theorem to non-prime modulus. Jun 4, 2016 at 10:58
• Unfortunately no!! Jun 4, 2016 at 10:59
• It says that modulo $n$, the exponent $\phi(n)$ is special ($\phi$ is the Euler totient function), and creates $1$ as long as the base of the power is coprime with $n$. It just so happens that if $n$ is a prime, then $\phi(n)=n-1$, and every non-zero residue becomes coprime, which turns the statement into Fermat's theorem. Jun 4, 2016 at 11:05
• @Arthur Thank you dear Jun 4, 2016 at 11:06
• Direct calculation is always possible. Whether there is any sensible middle ground depends heavily on exactly which theorems you know and are comfortable with. You might find something if you look hard enough, but at that point, what's the point? Jun 4, 2016 at 11:10

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

• ... $x^6\equiv x$ as long as $9$ and $x$ are coprime, that is. Jun 4, 2016 at 11:01
• I think $x^7\equiv{x}\pmod9$ is correct!! Jun 4, 2016 at 11:10
• You're right, it should've been $x^6\equiv 1$, and my eyes are lowered for making such a mistake and not catching it in time. However, the focus of my comment was not the exponent, but the relationship between $x$ and $9$. Jun 4, 2016 at 11:13

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.

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