# Pattern to last three digits of power of $3$?

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?

• Note sure if it will help but $3^{27} = 3^{3^3}$. – gt6989b Apr 9 '13 at 12:48

\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}

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

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.

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

• Using Mathematica, I would recommend Mod[3^Range[27],1000] – KennyColnago Apr 9 '13 at 15:35

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.

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, 667


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 a pattern isn't immediately spottable is in the 100s digit. If you check carefully though, you can see a recurrence every 5 lines (adding $4, 2, 6, 8$ to the previous set of 5 lines): (0, 0, 5, 4, 7) + 4 = (4, 4, 9, 8, 1).

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.

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.