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.


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

  • $\begingroup$ 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! $\endgroup$ – kayeomans Feb 17 '14 at 19:07
  • $\begingroup$ @kayeomans, my pleasure. Added a few Related $\endgroup$ – lab bhattacharjee Feb 17 '14 at 19:10
  • $\begingroup$ @kayeomans One can do it even more simply - see my answer. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.