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

-

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.

-

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

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.

-

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.

-