2
$\begingroup$

Find the last two digits of a sum of eighth powers of $100$ consecutive integers.

Attempt:

Since $(100k+x)^8 \equiv x^8 \pmod{100}$, we solely need to find $S=1^8+2^8+\cdots+100^8 \pmod{100}$. By the Chinese Remainder Theorem, if we determine the sum modulo $4$ and modulo $25$, we will know it modulo $100$. Taking it modulo $4$ we have $S \equiv 1+0+1+\cdots+1+0 \equiv 50 \equiv 2 \pmod 4$.

Now, since the number of units modulo $25$ is $\phi(25)$ and $\gcd(8,\phi(25)) = 4$, does that mean we can replace the sum of the $8$-th powers mod $25$ by the sum of the $4$-th powers mod $25$?

$\endgroup$
  • $\begingroup$ Hint: $a^8=(k-a)^8 mod k$ Now how can this be of use to calculate your congruence? $\endgroup$ – Bahbi May 15 '16 at 14:41
1
$\begingroup$

I don't know about your last argument, but the problem is not that complicated if you consider the following reductions:

  • to compute $1^8+...+100^8$ modulo $25$ it suffices to find $1^8+...+25^8$ modulo $25$ and multiply the result by $4$.
  • to compute $1^8+...+25^8$ modulo $25$ it suffices to find $1^8+...+12^8$ modulo $25$ and multiply the result by $2$ and this is not too long

I guess you may find a more elegant solution using rings of the form $(\Bbb{Z}/n\Bbb{Z})$.

$\endgroup$
  • $\begingroup$ Cant we take mod 10 upto 10 and multiply by 10? $\endgroup$ – N.S.JOHN May 15 '16 at 17:15
  • $\begingroup$ Yes, that might work also. :) $\endgroup$ – Beni Bogosel May 15 '16 at 18:57
  • $\begingroup$ So wouldn't the answer be 0 as we are multiplying 10? $\endgroup$ – N.S.JOHN May 16 '16 at 2:55
  • $\begingroup$ We want to find the last two digits, not only the last one. $\endgroup$ – Beni Bogosel May 16 '16 at 9:15
  • $\begingroup$ @Beni Bogosel: $1+2^8+3^8+4^8+....+25^8=504 213 653 645=20 168 546 145\cdot 25+20$ and $20\cdot 4=80$. The problem is that $80\ne 30$. Regards. $\endgroup$ – Piquito May 16 '16 at 16:26
0
$\begingroup$

If $N=100M+ab$ then $N^8\equiv (ab)^8\pmod{100}$ so the question concerns the integers of the form $10a+b$ where $a$ and $b$ are digits.

Because of $(10a+b)^8\equiv 80ab^7+b^8 \pmod{100}$, we use this table modulo $100$ for calculations $$\begin{array}{|c|c|}\hline a & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0\\\hline a^7 & 1 & 28 & 87 & 84 & 25 & 36&43&52&69&00\\\hline a^8&1&56&61&36&25&16&01&16&21&00\\\hline\end{array}$$ Take the sum of ten consecutive eight powers $$S_x=(10a+x)^8+(10a+x+1)^8+(10a+x+2)^8+(10a+x+3)^8+(10a+x+4)^8+(10a+x+5)^8+(10a+x+6)^8+(10a+x+7)^8+(10a+x+8)^8+(10a+x+9)^8$$ One has $$S_x\equiv {80a[x^7+(x+1)^7+...+(x+9)^7]+[x^8+(x+1)^8+…+(x+9)^8]}\pmod{100}$$ Calculation gives $$S_0\equiv {80a(25)+33}\equiv 33\pmod{100}\\S_1 \equiv {80a(25)+33}\equiv 33\pmod{100}\\S_2 \equiv {80a(95)+13}\equiv 13\pmod{100}\\S_3 \equiv {80a(75)+53}\equiv 53\pmod{100}\\S_4 \equiv {80a(5)+13}\equiv 13\pmod{100}\\S_5 \equiv {80a(25)+33}\equiv 33\pmod{100}\\S_6 \equiv {80a(75)+33}\equiv 33\pmod{100}\\S_7 \equiv {80a(95)+13}\equiv 13\pmod{100}\\S_8 \equiv {80a(25)+53}\equiv 53\pmod{100}\\S_9 \equiv {80a(5)+13}\equiv 13\pmod{100}$$ We see the sum of ten consecutive eight powers beginning by $(10a+x)^8$ is independent of $a$ modulo $100$. It follows $$\sum_{k=0}^{99}(10a+x+k)^8=\sum_{k=0}^9(10a+x+k)^8+ \sum_{k=10}^{19}(10a+x+k)^8+\sum_{k=20}^{29}(10a+x+k)^8+...+\sum_{k=90}^{99}(10a+x+k)^8\equiv \underbrace{(S_x+S_x+…+S_x)}_{10\text{ times}}\equiv 10S_x\pmod{100}$$ According to the calculation above we have $10S_x\in\{330,130,530\}$ Thus $$\sum_{k=0}^{99}(10a+x+k)^8\equiv \color{red}{30}\pmod {100}$$

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