1
$\begingroup$

If $n$ is a positive integer, find the remainder of the following number divided by $100$: $$S = \sum_{i=0}^{99} (n+i)^6 + 2^{2^{2558}} + 1$$

I've wrote a program using logarithmic exponentiation and big integers to find that $2^{2^{2558}} \equiv 16 \pmod{100}$. But I don't know what can I do with $\sum_{i=0}^{99} (n+i)^6$. Can you help me continue the problem, please? Thanks!

$\endgroup$
3
  • 1
    $\begingroup$ Note that the remainder of the sum on division by 100 is the same for all n. For the first, that's not the indetended approach. Do you know about congruences? $\endgroup$
    – quid
    Jul 18 '18 at 18:57
  • $\begingroup$ Yes, a little. Do you mean there's a more elegant way to find the remainder of $2^{2^{2558}}$ divided by $100$? $\endgroup$ Jul 18 '18 at 19:00
  • 1
    $\begingroup$ much more elegant. $2^{20}=1\mod 25$. $2^4\equiv 1\mod 5$ so $2^{2558}\equiv 2^2=4\mod 5$. $2^{2558}\equiv 0 \mod 4$ so $2^{2558}\equiv 16\mod 20$. so $2^{2^{2558}}\equiv 2^{16}=256*256\equiv 36\equiv 11\mod 25$. And $2^{2^{2558}}\equiv 0 \mod 4$ so $2^{2^{2558}}\equiv 36\mod 100$. Unless I made an arithmetic error which is very likely. $\endgroup$
    – fleablood
    Jul 18 '18 at 19:35
1
$\begingroup$

First note that $$k^6+(k+1)^6+(k+2)^6+(k+3)^6\cong 2\quad\text{mod 4}$$ since$$k^6+(k+1)^6+(k+2)^6+(k+3)^6\cong1^6+2^6+3^6+4^6\cong2\qquad \text{mod 4}$$since we have $25$ of such 4-tuple terms we can say that $$\sum_{i=0}^{99}(n+i)^6\cong 2\quad\text{mod 4}$$also divisible by 25 since $$\sum_{i=0}^{24}(n+i)^6\cong\sum_{i=0}^{24}i^6=\sum_{i=1}^{24}i^6\text{mod 25}$$and since $$i^6\cong(25-i)^6\text{mod 25}$$ it suffices to show that $$\sum_{i=1}^{12}i^6\text{mod 25}$$or $$1^6+2^6+3^6+4^6+6^6+7^6+8^6+9^6+11^6+12^6\cong 0\text{mod 25}$$but this is true since $$25|1+7^6\\25|3^6+4^6\\25|2^6+11^6\\25|6^6+8^6\\25|9^6+12^6$$which completes our proof since $$\sum_{i=0}^{99}(n+i)^6=\sum_{i=0}^{24}(n+i)^6+\sum_{i=25}^{49}(n+i)^6+\sum_{i=50}^{74}(n+i)^6+\sum_{i=75}^{99}(n+i)^6\cong 0\quad\text{mod 25}$$

From the other side, $2^{2^{2558}}$ is divisible by 4 and we have $$2^7\cong3\quad\text{mod 25}\\2^{21}\cong27\cong 2\quad\text{mod 25}\\2^{20}\cong1\quad\text{mod 25}$$to find the remainder of division of $2^{2^{2558}}$ note that $$2^2\cong -1\quad\text{mod 5}$$here we obtain$$2^{2556}\cong 1\quad\text{mod 5}$$therefore $$2^{2558}\cong 4\quad\text{mod 20}$$finally by defining ${2^{2558}}=20u+4$ we conclude that $$2^{2^{2558}}=2^{20u+4}=16\cdot (2^20)^u\cong 16\cong -9\quad\text{mod 25}$$since $2^{2^{2558}}$ is also divisible by 4 we finally get$$2^{2^{2558}}=100k+16$$which means that $$\Large S\cong-33\quad\text{mod 100}$$

$\endgroup$
1
  • $\begingroup$ It's easy to show that $\sum_{i=0}^{99}(n+i)^6 \equiv 50 \pmod{100}$. $\endgroup$
    – Math Lover
    Jul 18 '18 at 19:28
1
$\begingroup$

If you know how to calculate the least universal exponent or Carmichael function $\lambda$, you know that $\lambda(100)=20$ and $\lambda(20)=4$ and thus

$2^{\large 2^{2558}}\equiv 2^{\large (2^{2558} \bmod 20)}\equiv 2^{\large (2^{2558 \bmod 4} \bmod 20)}\equiv 2^{\large (2^2\bmod 20)}\equiv 2^4 \equiv 16 \bmod 100$

Note that the $(n+i)$ term will take on every residue value $\bmod 100$ exactly once, no matter what the value of $n$ is. So there is only one answer, rather than a function based on $n$, and we can simply consider

$$S\equiv \left (\sum_{i=0}^{99} i^6 + 16 + 1 \right )\bmod 100$$

By reviewing the expansion it's clear that $i^6\equiv (50-i)^6\equiv (50+i)^6 \equiv (100-i)^6\bmod 100$ . Then

$$S\equiv\left( 4\sum_{i=1}^{24} i^6 + 2\cdot 25^6 + 17 \right )\bmod 100$$

Clearly $25^k\equiv 25 \bmod 100$ for $k>0$. Now there's probably something smart to do with that remaining sum, but I can't see it it immediately. It's pretty clear to me from considering primitive roots that the sum of all sixth powers $\bmod 100$ will be the same as the sum of all squares, but a little hard to prove briefly. Nevertheless I enlisted the help of a spreadsheet to show

$$\sum_{i=1}^{24} i^6 \equiv 0 \bmod 100$$

Thus

$$S\equiv\left( 4\cdot 0 + 2\cdot 25 + 17 \right ) \equiv 67 \bmod 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.