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!
\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}
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
Mod[3^Range[27],1000]
$\endgroup$
Apr 9, 2013 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.
