5
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ Do you know of Euler's theorem? It expands Fermat's theorem to non-prime modulus. $\endgroup$
    – Arthur
    Jun 4, 2016 at 10:58
  • $\begingroup$ Unfortunately no!! $\endgroup$ Jun 4, 2016 at 10:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – Arthur
    Jun 4, 2016 at 11:05
  • $\begingroup$ @Arthur Thank you dear $\endgroup$ Jun 4, 2016 at 11:06
  • 2
    $\begingroup$ 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? $\endgroup$
    – Arthur
    Jun 4, 2016 at 11:10

3 Answers 3

7
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ ... $x^6\equiv x$ as long as $9$ and $x$ are coprime, that is. $\endgroup$
    – Arthur
    Jun 4, 2016 at 11:01
  • 1
    $\begingroup$ I think $x^7\equiv{x}\pmod9$ is correct!! $\endgroup$ Jun 4, 2016 at 11:10
  • $\begingroup$ 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$. $\endgroup$
    – Arthur
    Jun 4, 2016 at 11:13
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.