1

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!

gareth618
  • 793
  • 1
    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? – quid Jul 18 '18 at 18:57
  • Yes, a little. Do you mean there's a more elegant way to find the remainder of $2^{2^{2558}}$ divided by $100$? – gareth618 Jul 18 '18 at 19:00
  • 1
    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. – fleablood Jul 18 '18 at 19:35

2 Answers2

1

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

Mostafa Ayaz
  • 31,924
1

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

Joffan
  • 39,627