Is sum of digits of $3^{1000}$ divisible by $7$?

Question

I'm working on a little exercise I found in my high school book (printed in 2007) which is pretty complicated.

Is the sum of digits of $3^{1000}$ a multiple of $7$?

Do you have any advice to solve this type of problem (without programming of course!)

PS :

We are a group of 3 french people working on it since 2007.

The sum calculated with Python is 2142, this number is a multiple of 7 BUT we want a mathematical answer.

All the results below are mathematically proved !!

$3^{1000}$ has 478 digits and the sum of digits of $3^{1000}$ can't be superior to 4302 (9*478).

This sum is a multiple of 3 and 9.

The last digits of $3^{1000}$ are 0001 (math proof not a result of a computer calculation).

The one who created this exercise doesn't know the answer.

Please help us with any clue!

---

Cross-posted at https://mathoverflow.net/q/282035/22954 on MathOverflow.

Answer 1

Base-$10$ digit sums mod $7$ are, unfortunately, not particularly nicely behaved. The first hundred $n$ for which the sum of digits of $3^n$ is divisible by $7$ are $$ 25, 26, 30, 32, 47, 58, 79, 81, 87, 89, 102, 123, 141, 144, 145, 151, 164, 176, 178, 193, 201, 227, 239, 242, 257, 264, 282, 289, 300, 306, 319, 324, 329, 335, 336, 338, 348, 351, 358, 365, 395, 403, 437, 441, 450, 460, 468, 484, 489, 492, 495, 517, 518, 541, 542, 544, 554, 555, 563, 565, 570, 580, 587, 597, 601, 610, 617, 618, 620, 638, 639, 655, 659, 663, 671, 695, 720, 721, 745, 748, 755, 757, 772, 774, 781, 783, 789, 790, 797, 800, 805, 809, 813, 822, 826, 828, 841, 844, 850, 859$$ I don't see any pattern here.

Answer 2

I am not answering the question but the post asks for clues so here it is a couple of ideas.

If $a_0,a_1,a_2, \cdots , a_{477} $ are the decimal digits of $3^{1000}$ then the numbers $$b_i=a_{6i}+a_{6i+1}\cdot 10+a_{6i+2}\cdot 10^2+a_{6i+3}\cdot 10^3+a_{6i+4}\cdot 10^4+a_{6i+5}\cdot 10^5$$ for $i=0,1,2,\cdots, 79$ are the digits of $3^{1000}$ in base $10^6$ ($80$ is the nearest integer above $477 \div 6$ so there are $80$ digits numbered $0,1,2,\cdots,79$)

In other words: $$ 3^{1000} = b_0 + b_1 \cdot 10^6+ \cdots + b_{79} \cdot (10^6)^{79}$$

Now, if we resort to modular arithmetic we see that $$ 3^0=1, 3^1=3 , 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1 $$ (all the equalities taken modulo $7$).

Also $$3^{1000}=(3^6)^{166}\cdot 3^4= 1 \cdot 4 = 4$$(all the equalities taken modulo $7$).

Now if we note that $10^6=1$ (modulo 7) the expression of $3^{1000}$ in base $10^6$ reads (modulo 7) $$ 4=b_0+b_1+ \cdots +b_{79}$$

So we can assert that the sum of digits of $3^{1000}$ in base one milion gives a remainder of $4$ when divided by $7$.

Another partial result comes from the decimal expansion read modulo 7:

$$3^{1000}= a_0+ a_1 \cdot 10 + \cdots +a_{477} \cdot 10^{477} =1 = a_0+3 a_1+ 2a_2 + 6 a_3 + 4 a_4 + 5 a_ 5 + \cdots $$

So, given that $a_0=1$ we can say that this particular linear combination of the remaining digits is divisible by $7$.