0
$\begingroup$

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

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

4 Answers 4

0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Oooo, thanks a lot, that's great $\endgroup$
    – Karol
    Feb 20, 2020 at 12:43
0
$\begingroup$

Hint: Fermat's little theorem will be useful.

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

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

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

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

$\endgroup$

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