# Find the last two digits of $3^{45}$

I was wondering if there is a simpler way to find the last to digits of a power such as $3^{45}$. I reduced it modulo 100 to get the answer, which is 43. But I was curious if there was a simpler, or more eloquent way to get this result.

Here's my method:

Using the fact that $3^4=81\equiv -19 \pmod{100}$ and $19^5=2,476,099\equiv -1 \pmod{100}$

$$3^{45}\equiv 3(3^4)^{11}\equiv 3(-19)^{11}\equiv 3(-19)(19^5)^2\equiv 3(-19)(-1)^2 \equiv -57 \equiv 43 \pmod {100}$$

I just felt like this was sort of a messy way to find out that the last two digits are 43.

## 3 Answers

Essentially, we need to find $\displaystyle 3^{45}\pmod{100}$

Method $\#1:$

Now, $$3^{45}=3\cdot3^{44}=3(3^2)^{22}=3(10-1)^{22}=3(1-10)^{22}$$

Now, $$(1-10)^{22}\equiv1-10\cdot22\pmod{100}\equiv-19\equiv81$$

Method $\#2:$

As $(3,10)=1$

using Euler's Totient Theorem, $\displaystyle \phi(100)=40\implies 3^{40}\equiv1\pmod{100}$

or using Carmichael Function, $\displaystyle \lambda(100)=20\implies 3^{20}\equiv1\pmod{100}$

In either case, $\displaystyle3^{45}\equiv3^5\pmod{100}$

• That does simplify it much "prettier" than my method. I have just not been introduced to Euler's Totient Theorem or the Carmichael Function yet, although I assume we are building up to that soon. Thanks for the suggestions! – kayeomans Feb 17 '14 at 19:07
• @kayeomans, my pleasure. Added a few Related – lab bhattacharjee Feb 17 '14 at 19:10
• @kayeomans One can do it even more simply - see my answer. – Bill Dubuque Feb 17 '14 at 19:51

${\rm mod}\ 50\!:\ \color{#0a0}{3^5\equiv -7}\,\Rightarrow\,\color{#c00}{3^{10}}\equiv 49\equiv \color{#c00}{-1}\,\Rightarrow\,3^{45}\equiv \color{#0a0}{3^5}(\color{#c00}{3^{10}})^4\equiv \color{#0a0}{-7}(\color{#c00}{-1})^4\equiv -7,\,$ so $\,3^{45}\!\,$ is either $\,\equiv -7\,$ or $\,50\!-\!7\equiv 43\pmod{100}.\,$ It must be $\,43,\,$ by ${\rm mod}\ 4\!:\ 3^{45}\!\equiv (-1)^{45}\!\equiv -1\equiv 43.$

A simple method: If you write down the first 24 powers of 3, keeping just the last 2 digits, you get

1   3   9   27
81  43  29  87
61  83  49  47
41  23  69  7
21  63  89  67
1   3   9   27


After a few powers you realize that you only need the last 2 digits of some power of 3 to get the last 2 digits of the next power.

There is a clear pattern that it cycles every 20th power (note that the last digit cycles every 4th power: 1-3-9-7...). Therefore the last two digits of $3^{45}$ are the same as for $3^{25}$ and for $3^5=243$, i.e. 43.