Large number's modular operation

A well known rule for whether a number is divisible by $3$ is whether the sum of its digits is divisible by $3$ . This can be extended to: $n\bmod3=\text{digital root}(n)\bmod3$ This is easily proven by the fact that $10^n\div1$ has a remainder of $3$ for any positive integer $n$ . For example, we'll look at the number $478$ : $\begin{aligned}478\bmod3&=[400+70+8]\bmod3\\ &=[4\times(100\bmod3)+7\times(10\bmod3)+8]\bmod3\\ &=[4\times(1)+7\times(1)+8]\bmod3\\ &=[4+7+8]\end{aligned}$ So to find the remainder on dividing by $3$ of the large number in the question, we will find the remainder on dividing by $3$ of the digital root of the number: $122333444455555666666\dots10000000001000000000\dots1000000000\bmod3\\ =\text{digital root}(122333444455555666666\dots10000000001000000000\dots1000000000)\bmod3\\ =(1+2+2+3+3+3+4+4+4+4+\dots+1000000000+1000000000+\dots+1000000000)\bmod3\\ =(1+2\times2+3\times3+4\times4+\dots+1000000000\times1000000000)\bmod3\\ =(1+2^2+3^2+4^2+5^2+6^2+\dots+1000000000^2)\bmod3\\ =[(1\bmod3)+(2^2\bmod3)+(3^2\bmod3)+(4^2\bmod3)+(5^2\bmod3)+(6^2\bmod3)+\dots+(1000000000^2\bmod3)]\bmod3$ Now we have to see what remainder we get from each term on dividing by $3$ :

• If $n\bmod3=0$ , then $n^2\bmod3=\textbf{0}$
• If $n\bmod3=1$ , then $n^2\bmod3=(n\bmod3)^2\bmod3=1\bmod3=\textbf{1}$
• If $n\bmod3=2$ , then $n^2\bmod3=(n\bmod3)^2\bmod3=2^2\bmod3=4\bmod3=\textbf{1}$

This means we get a pattern of 1s and 0s in our sum: $[(1\bmod3)+(2^2\bmod3)+(3^2\bmod3)+(4^2\bmod3)+(5^2\bmod3)+(6^2\bmod3)+\dots+(1000000000^2\bmod3)]\bmod3\\ =1+1+0+1+1+0+1+1+0+\dots+1+1+0+1\bmod3$ Since 1000000000 divided by 3 gives 333333333 with remainder 1, our sum equals: $[(1+1+0)\times333333333+(1000000000^2\bmod3)]\bmod3\\ =(2\times333333333+1)\bmod3\\ =1$ Since 333333333 is divisible by three, this term disappears when taking the remainder on dividing by three, leaving only the 1 from the $1000000000^2$ .

Therefore the final answer is $\boxed{1}$ .

We have S(n) is congruent to 1^2+2^2+...+(10^9)^2. Note that n is congruent to S(n) mod 3. We know that every positive square is either divisible by 3 or leaves remainder 1. Hence, we have: S(n) congruent to 2*{[(10^9)-1] /3}+1 S(n) congruent to 1 mod 3 since 9 divides 10^9-1 Therefore, n is congruent to 1 mod 3. Is something wrong with this solution?