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??
$\begingroup$
$\endgroup$
6
This site has become a dump.
58.7k7 gold badges69 silver badges154 bronze badges
asked Jun 4, 2016 at 10:54
-
2$\begingroup$ Do you know of Euler's theorem? It expands Fermat's theorem to non-prime modulus. $\endgroup$– ArthurJun 4, 2016 at 10:58
-
$\begingroup$ Unfortunately no!! $\endgroup$– Hamid Reza EbrahimiJun 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$– ArthurJun 4, 2016 at 11:05
-
$\begingroup$ @Arthur Thank you dear $\endgroup$– Hamid Reza EbrahimiJun 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$– ArthurJun 4, 2016 at 11:10
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
3
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}.$$
answered Jun 4, 2016 at 10:58
This site has become a dump.This site has become a dump.
58.7k7 gold badges69 silver badges154 bronze badges
-
1$\begingroup$ ... $x^6\equiv x$ as long as $9$ and $x$ are coprime, that is. $\endgroup$– ArthurJun 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$– ArthurJun 4, 2016 at 11:13
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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$$
answered Nov 5, 2020 at 0:09