Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm wondering if there is a pattern to the last three digits of a a power of $3$? I need to find out the last three digits of $3^{27}$, without a calculator.

I've tried to find a pattern but can not see one? Am I missing something?

Thanks for your help in advance!

share|improve this question
1  
Note sure if it will help but $3^{27} = 3^{3^3}$. –  gt6989b Apr 9 '13 at 12:48

7 Answers 7

up vote 32 down vote accepted

\begin{align} 3^{27}=3(3^{26})=3(9^{13})& =3(10-1)^{13} \\ & \equiv 3((-1)^{13}+13(-1)^{12}(10)+\binom{13}{2}(-1)^{11}(10^2)) \pmod{1000} \\ & \equiv 3(-1+130-7800) \pmod{1000} \\ & \equiv 987 \pmod{1000} \\ \end{align}

Edit: The same method (using binomial theorem) can easily be applied to $3^n$, even for large $n$.

\begin{align} 3^{2n}=9^n & =(10-1)^n \\ & \equiv (-1)^n+n(-1)^{n-1}(10)+\binom{n}{2}(-1)^{n-2}(10^2)) \pmod{1000} \\ & \equiv (-1)^n(1-10n+100\binom{n}{2}) \pmod{1000} \\ \end{align}

\begin{align} 3^{2n+1}=3(3^{2n}) \equiv 3(-1)^n(1-10n+100\binom{n}{2}) \pmod{1000} \\ \end{align}

share|improve this answer
    
One more vote for Gerry and you get a gold badge I think :) I'll do it in the morning when I have more votes –  muzzlator Apr 11 '13 at 14:15
    
@muzzlator: No, the accepted answer needs to have a vote total of strictly more than 10 for that badge to drop. –  Henning Makholm Apr 11 '13 at 17:13
    
@HenningMakholm Ah, looks like someone else will have to stumble upon this question too then –  muzzlator Apr 11 '13 at 17:23
    
@learner $$-23013 \equiv 987 \pmod{1000}$$ –  Ivan Loh Nov 21 '13 at 12:31

If you can multiply a 3-digit number by $3$ without a calculator, then you can answer the question without a calculator. Just start with $1$, multiply by $3$ $27$ times, keeping only the last three digits. $1,3,9,27,81,243,729,187$, and so on.

share|improve this answer

There will be a pattern to the last three digits of a power of 3, in general. However, that pattern may not necessarily show itself within the first 27 terms.

However, here's something you can do instead to solve your problem: $$\begin{align} \text{ last 3 digits of } 3^{27} &= \text{ last 3 digits of } (3^3)^9\\ &= \text{ last 3 digits of } 27^9\\ &= \text{ last 3 digits of } (27^3)^3\\ &= \text{ last 3 digits of } 19683^3\\ &= \text{ last 3 digits of } 683^3\\ &= \text{ last 3 digits of } 318611987\\ &= 987 \end{align} $$

Not the most elegant solution, but it does reduce the number (and difficulty) of the multiplications required to solve the problem.

share|improve this answer

Exponentiation by squaring reduces the number of multiplications from 26 to 7:

First square repeatedly to create powers by powers of 2:

$$ 3^1=3 \qquad 3^2=9 \qquad 3^4=81 \qquad 3^8 \equiv 561 \pmod{1000} \qquad 3^{16} \equiv 721 \pmod{1000} $$

Then, since $27=1+2+8+16$,

$$ 3^3=3^1 3^2 = 27 \qquad 3^{11} = 3^3 3^8 \equiv 147 \pmod{1000} \qquad 3^{27} = 3^{11} 3^{16} \equiv 987 \pmod{1000} $$


We can even be smarter, as gt6989b noted in a comment, and use $3^{27} = ((3^3)^3)^3$ and get down to 6 multiplications:

$$ 3^2 = 9 \qquad 3^3 = 27 $$ $$ (3^3)^2 = 729 \qquad 3^9 = (3^3)^3 \equiv 683 $$ $$ (3^9)^2 \equiv 489 \qquad 3^{27} = (3^9)^3 \equiv 987 $$

But in general the trouble of looking for such tricks is not really worth it over just using plain squaring.

share|improve this answer

Well I don't see a pattern here $$\{3,9,27,81,243,729,187,561,683,49,147,441,323,969,907,721,163,489,467,401,203,609,827,481,443,329,987\}$$

Created with Mathematica with the command

Table[If[k < 5, 3^k, FromDigits[IntegerDigits[3^k][[-3 ;; -1]]]], {k, 1, 27}]

In principle you calculate $3^k $ mod 1000, as 3 and 1000 are coprimes, there will be a pattern for sure, but the length of a period could be something up to 1000, which doesn't really help you.

Here the lenght of the period is 100, so the following numbers are recurring

3,9,27,81,243,729,187,561,683,49,147,441,323,969,907,721,163,489,467,401,203,609,827,481,
443,329,987,961,883,649,947,841,523,569,707,121,363,89,267,801,403,209,627,881,643,929,787,
361,83,249,747,241,723,169,507,521,563,689,67,201,603,809,427,281,843,529,587,761,283,849,
547,641,923,769,307,921,763,289,867,601,803,409,227,681,43,129,387,161,483,449,347,41,123,
369,107,321,963,889,667,1,3
share|improve this answer
1  
Using Mathematica, I would recommend Mod[3^Range[27],1000] –  KennyColnago Apr 9 '13 at 15:35

If we generate the list, and format it appropriately, some patterns immediately become apparent:

001, 003, 009, 027, 
081, 243, 729, 187, 
561, 683, 049, 147, 
441, 323, 969, 907, 
721, 163, 489, 467, 
401, 203, 609, 827, 
481, 443, 329, 987, 
961, 883, 649, 947, 
841, 523, 569, 707, 
121, 363, 089, 267, 
801, 403, 209, 627, 
881, 643, 929, 787, 
361, 083, 024, 747, 
241, 723, 169, 507, 
521, 563, 689, 067, 
201, 603, 809, 427, 
281, 843, 529, 587, 
761, 283, 849, 547, 
641, 923, 769, 307, 
921, 763, 289, 867, 
601, 803, 409, 227, 
681, 043, 129, 387, 
161, 483, 449, 347, 
041, 123, 369, 107, 
321, 963, 889, 067

The units are always odd (obviously), and increase by $2, 6, 8, 4$

The 10s in each column is increasing by the same amount on each row (again, $8, 4, 2, 6$)

The only place I can't immediately spot any pattern is in the 100s digit.

Interestingly, $2, 4, 8, 6$ are the only values of $2^n mod 10, n>0$. There's some significance there, but it's been a while since I studied number theory.

share|improve this answer

Since $1000 = 2^3 5^3$, and those factors are relatively prime, you can determine $3^n \mod 1000$ by determining $3^n \pmod 8$ and $3^n \pmod {125}$,

$3^n \pmod 8$ is easy, as $3^2 = 9 \equiv 1 \pmod 8$.

$3^n \pmod {125}$ is tedious. Work with smaller powers of $5$ as exponent first:

$3^4 \equiv 1 \pmod 5$. The exponent must divide $\phi(5) = 4$.

$3^{20} \equiv 1 \pmod{25}$. The exponent must divide $\phi(25) = 20$ and be a multiple of $4$ from the above.

$3^{20} \equiv 26 \pmod {125}$. I cheated and used a calculator. But $3^{100} \equiv 1 \pmod {125}$. The exponent must divide $\phi(125) = 100$ and be a multiple of $20$.

So, $3^{27} \equiv 3 \pmod 8$ and $3^{27} \equiv 26\cdot3^7 \pmod {125}$.

$3^5 = 243 \equiv -7 \pmod {125}$. $3^7 \equiv -7 \cdot 9 \equiv -63 \equiv 62 \pmod {125}$. So $3^{27} \equiv 26 \cdot 62 \pmod {125}$.

Use the Chinese Remainder Theorem.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.