Calculate $27^{162} \pmod {41}$

Question

Calculate: $27^{162} \pmod {41}$

So we need to calculate x which is a remainder of $$\frac{27^{162}}{41}$$

$27 = 3^3$ so we can write such equation: $$3^{486} = 41k + x$$ or $$3^{3 \times 162} = 41k + x$$ where x is a reminder.

But what do I do next to calculate this without using calculator(or using simple one)?

Answer 1

By Fermat's Little theorem, $$27^{40}\equiv1\pmod{41}$$ So, $$(27^{40})^4\equiv1^4\equiv1\pmod{41}$$ Hence, $$27^{162}=(27^{40})^4\times 27^2\equiv 27^2\pmod{41}$$

Answer 2

Hint: Fermat's little theorem will be useful.

Answer 3

As $27=3^3,$

$$27^{162}=(3^3)^{162}=3^{486}$$

Now as $(3,41)=1$ and $\phi(41)=40,486\equiv6\pmod{\phi(41)}$

$$3^{486}\equiv3^6\pmod{41}\equiv(3^3)^2\equiv(-14)^2\equiv196\equiv-9\equiv32$$

Answer 4

Notice that $$3^4 = 81 \equiv -1 \quad (\text{mod } 41) $$ so $$3^{486} = (3^4)^{121}\cdot 3^2 \equiv (-1)^{121}\cdot 9 = -9 \equiv 32 \quad (\text{mod } 41) $$