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

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.

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

• What is the name of the book – lab bhattacharjee Sep 17 '17 at 16:00
• @Lezraf Since $2007$? A computer program can do it fairly quickly - it's less than $500$ digits. – Thomas Andrews Sep 17 '17 at 16:01
• Yeah, we already calculated it with python, the sum is 2142 and it is a multiple of 7. But we are looking for a mathematical method...that question was in a maths book. the problem should be solved analytically! – Lezraf Sep 17 '17 at 16:10
• 3P1000=1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001, the sum is 2142. I have many other data if anyone need it. – Lezraf Sep 17 '17 at 18:00
• @Lezraf you should include some of your comments into you question. (say, the part about "working on it since 2007", "know the digit sum is 2142 and want a mathematical answer" and "even the teacher don't know the answer" ) This will make the question much more complete. – achille hui Sep 21 '17 at 9:24

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

• I remember to have calculated $500$ digits for $3^{1000}$ two days ago. Was I wrong? – Piquito Sep 28 '17 at 1:23
• In base $10^6$ there are $10^6$ "digits".....($10^{18}$ is written $1000$ so is it $0+0+0+1\equiv4\pmod 7$? – Piquito Sep 28 '17 at 1:32
• I don't understand your last claim "given $a_0 = 1$, we can say... divisible by $7$". – achille hui Sep 28 '17 at 11:01
• To @achillehui: We know that the first digit of $3^{1000}$ is $1$ so $a_1+ 2a_2 + 6 a_3 + 4 a_4 + 5 a_ 5 + \cdots=0$ modulo $7$ – Arundo Donax Sep 28 '17 at 16:21
• @ArundoDonax oh, I see what you mean now. – achille hui Sep 28 '17 at 16:56

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.

• I would like so much to have your methods for numerical calculation.....Regards. – Piquito Sep 26 '17 at 23:54
• @Piquito It's very easy in Maple: convert(convert(3^n, base, 10), +); – Robert Israel Sep 27 '17 at 4:28
• Robert, how far can you push your calculations, I would like to see as many $n$ as possible.? – user480281 Sep 27 '17 at 5:03
• For example, $3^{1000000}$ took about $50$ seconds on my computer: the sum is $2146509$, which is not divisible by $7$. – Robert Israel Sep 27 '17 at 5:30
• We have $$ds_{10} (3^{12348})=26397$$ Here both an exponent and the resull are divisible by 7. Maybe not important, just mentioning in case you also study this sequence and seek for curiosities. – user480281 Sep 27 '17 at 6:08