Intereting Posts

Show that the angles satisfy $x+y=z$
Prove that the product of four consecutive positive integers plus one is a perfect square
Expected number of steps to transform a permutation to the identity
Game Theory and Uniform Distribution question?
Finitely Presented is Preserved by Extension
Is the unit sphere in $(C, \| \cdot\|_1)$ compact?
The union of growing circles is not homeomorphic to wedge sum of circles
Elegant proofs that similar matrices have the same characteristic polynomial?
Show $\{0^m1^n | m \neq n\}$ is not regular
Do Convergence in Distribution and Convergence of the Variances determine the Variance of the Limit?
$\langle r\rangle$ maximal $\iff r$ irreducible
Cyclic group order 15
Fly and Two Trains Riddle
How to compute the sum $ 1+a(1+b)+a^2(1+b+b^2)+a^3(1+b+b^2+b^3)+\cdots$
Integral solutions to $y^{2}=x^{3}-1$

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!

- Order of $5$ in $\Bbb{Z}_{2^k}$
- To prove that $ + ++\dots ++$ is even.
- Solving $ax \equiv c \pmod b$ efficiently when $a,b$ are not coprime
- Can you determine a formula for this problem?
- Show that 7 is a quadratic residue for any prime p of the form 28k + 1 and 28k + 3.
- Math olympiad 1988 problem 6: canonical solution (2) without Vieta jumping

- Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power
- complete residue system modulo $p$
- If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$.
- Prove that, for any natural number $k$ $\exists m \in M $ s.t i) $m$ has exactly $k$ $1$'s, an
- Integers that satisfy $a^3= b^2 + 4$
- What is a negative number?
- $\forall A\subset \mathbb{N}$ the sum of the reciprocals of $A$ diverges iff $A$ is $(\tau, \mathbb{N})$-dense
- Finding all integers such that $a^2+4b^2 , 4a^2+b^2$ are both perfect squares
- Show that there is no integer n with $\phi(n)$ = 14
- Can an odd perfect number be divisible by $105$?

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

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.

- Closure of the invertible operators on a Banach space
- Fundamental group of a torus with points removed
- Does a “cubic” matrix exist?
- When is $\sin(x)$ rational?
- The Instant Tangent
- If $\limsup x_n = x$, $\lim y_n = y$, $x_n, y_n > 0$, then does $\limsup (x_n y_n)= xy$?
- Covering space is a fiber bundle
- Inductive proof of the closed formula for the Fibonacci sequence
- Understanding AKS
- to prove $f(P^{-1}AP)=P^{-1}f(A)P$ for an $n\times{n}$ square matrix?
- Why $f\colon \mathbb{Z}_n^\times \to \mathbb{Z}_m^\times$ is surjective?
- Average distance between two random points in a square
- Evaluate this and also the indefinite case
- What's are all the prime elements in Gaussian integers $\mathbb{Z}$
- Describe all the complex numbers $z$ for which $(iz − 1 )/(z − i)$ is real.