38
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What is the name of the book $\endgroup$ – lab bhattacharjee Sep 17 '17 at 16:00
  • 6
    $\begingroup$ @Lezraf Since $2007$? A computer program can do it fairly quickly - it's less than $500$ digits. $\endgroup$ – Thomas Andrews Sep 17 '17 at 16:01
  • 2
    $\begingroup$ 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! $\endgroup$ – Lezraf Sep 17 '17 at 16:10
  • 5
    $\begingroup$ 3P1000=1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001, the sum is 2142. I have many other data if anyone need it. $\endgroup$ – Lezraf Sep 17 '17 at 18:00
  • 5
    $\begingroup$ @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. $\endgroup$ – achille hui Sep 21 '17 at 9:24
3
+300
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I remember to have calculated $500$ digits for $3^{1000}$ two days ago. Was I wrong? $\endgroup$ – Piquito Sep 28 '17 at 1:23
  • $\begingroup$ In base $10^6$ there are $10^6$ "digits".....($10^{18}$ is written $1000$ so is it $0+0+0+1\equiv4\pmod 7$? $\endgroup$ – Piquito Sep 28 '17 at 1:32
  • 1
    $\begingroup$ I don't understand your last claim "given $a_0 = 1$, we can say... divisible by $7$". $\endgroup$ – achille hui Sep 28 '17 at 11:01
  • $\begingroup$ 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$ $\endgroup$ – Arundo Donax Sep 28 '17 at 16:21
  • $\begingroup$ @ArundoDonax oh, I see what you mean now. $\endgroup$ – achille hui Sep 28 '17 at 16:56
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would like so much to have your methods for numerical calculation.....Regards. $\endgroup$ – Piquito Sep 26 '17 at 23:54
  • 1
    $\begingroup$ @Piquito It's very easy in Maple: convert(convert(3^n, base, 10), `+`); $\endgroup$ – Robert Israel Sep 27 '17 at 4:28
  • $\begingroup$ Robert, how far can you push your calculations, I would like to see as many $n$ as possible.? $\endgroup$ – user480281 Sep 27 '17 at 5:03
  • $\begingroup$ For example, $3^{1000000}$ took about $50$ seconds on my computer: the sum is $2146509$, which is not divisible by $7$. $\endgroup$ – Robert Israel Sep 27 '17 at 5:30
  • $\begingroup$ 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. $\endgroup$ – user480281 Sep 27 '17 at 6:08

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.