Using Euler Totient to compute digits in $3^{40000005}$

Question

I'm trying to computer the two rightmost digits in $3^{40000005}$. Can this be done using the Euler Totient function alone as:

For every digit $m >1$,

$$m = \prod_{i = 1}^{n}p_i^{e_i}$$ where the $p_i$'s are distinct primes and $e_i$ > 0, then the Euler Totient function is:

$$ \phi(m) = \prod_{i = 1}^{n}(p_i^{e_i}-p_i^{e_i-1})$$

Answer 1

Well, yes, you can calculate $\varphi(100)$, that will be a period of powers of $3$ modulo $100$.

We are looking for the last two digits, ie. the remainder modulo $100$ of $3^{400..005}$.

By the Euler-Fermat theorem, as $3$ is coprime to $100$, we know that $3^{\varphi(100)}\equiv 1\pmod{100}$.

Then find the remainder $r$ of the exponent modulo $\varphi(100)$ and the answer will be the same as the last two digits of $3^r$.

$\varphi(100)=\varphi(2^2\cdot 5^2)=2\cdot1\cdot5\cdot4=40$
$400..005\equiv 5\pmod{40}$
$3^{400..005}\equiv (3^{40})^{100...}\cdot 3^5\equiv 1\cdot 3^5=81\cdot 3=243\equiv {\bf 43} \pmod{100}$

Answer 2

I am not aware of the Euler Totient function. But your answer can be computed easily using modular arithmetic.

$$ 3^2\equiv (-1)\pmod {10}$$ since $a\equiv b\pmod {n} \implies a^k\equiv b^k\pmod {n};$ $$ (3^2)^{20000002}\equiv (-1)^{20000002}\pmod {10}$$ $$ 3^{40000004}\equiv 1\pmod {10}$$ since $ a\equiv b\pmod {n} \implies c \times a\equiv c \times b\pmod {n}$ $$ 3\times3^{40000004}\equiv 3\pmod {10}$$

Therefore the final digit of the number $3^{40000005}$ is $3$.

Answer 3

The answer via Isfaaq's proposed technique goes as follows. You have $3^{60} \hbox{ mod } 100 = 1.$ Also, $40000005 \hbox{ mod } 60 = 45.$ Therefore, $$ 3^{40000005} \hbox{ mod } 100 = 3^{45} \hbox{ mod } 100 = 43.$$

Answer 4

Using Carmichael function, $\displaystyle\lambda(100)=20$ and $\displaystyle40000005\equiv5\pmod{20}$

$\displaystyle\implies 3^{40000005}\equiv3^5\pmod{100}$

---

Alternatively, $\displaystyle3^{40000005}=3(10-1)^{20000002}$

$=3(1-10)^{20000002}\equiv 3(1-20000002\cdot10)\pmod{100}$ (as the higher terms contains $10^2$ as factor)

$\displaystyle\equiv3(1-20)\equiv-57\equiv43$