# Calculate $27^{162} \pmod {41}$ [duplicate]

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)?

• Is the exponent 162 or 169? Feb 20, 2020 at 12:39
• 162 let me edit that quictly Feb 20, 2020 at 12:39
• $27^{40}=1$ modulo $41$ and $162=40\cdot4+2$ Feb 20, 2020 at 12:47

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

• Oooo, thanks a lot, that's great Feb 20, 2020 at 12:43

Hint: Fermat's little theorem will be useful.

• I'm not quite sure how to apply it Feb 20, 2020 at 12:41
• $27^{40}\equiv1\bmod41$ Feb 20, 2020 at 12:54

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

• What is $\phi(41)$? I mean what is $\phi()$ Feb 20, 2020 at 12:45
• @Karol It is the Euler's totient function. Feb 20, 2020 at 12:48

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