Raising $2$ to the power of $2014^ {2013}$ modulo $41$

Question

The question is as follows: $$2^{{2014}^{2013}}$$ Determine its remainder by division with $41$. I know that I need to use $\bmod 41$ and reduce the power somehow to something that can be solved easily but I am not able to figure out how. There is a hint too. $$2^{10} \equiv -1 \pmod{41}$$ which I think I need to incorporate somewhere but I do not know how. How should I go about this problem?

Answer 1

So, $2^{20}\equiv(-1)^2\equiv1\pmod{41}$

$$2014^{2013}\equiv14^{2013}\pmod{20}$$

Now as $(14^n,20)=4$ for $n\ge2$

let us find $14^{2013-2}\pmod{\dfrac{20}4}$ i.e., $14^{2001}\pmod5$

As $14\equiv-1\pmod5,14^{2001}\equiv(-1)^{2001}\equiv-1$

As $a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod{m\cdot c},$

$14^2\cdot14^{2011}\equiv14^2(-1)\pmod{14^2\cdot5}$

As $20|14^2\cdot5,14^{2013}\equiv-14^2\pmod{20}\equiv4\implies14^{2013}=20a+4$

$2^{14^{2013}}=2^{20a+4}=(2^{20})^a\cdot2^4\equiv1^a\cdot2^4\pmod{41}$

Answer 2

Here's how to use the hint: Since $2^{10}$ = -1 (mod 41), you have $2^{20}$ = 1 (mod 41). So if you knew $2014^{2013}$ modulo 20, you'd have the result immediately. So how do you get $2014^{2013}$ modulo 20? That's obviously $(-6)^{2013}$ modulo 20.

Answer 3

$\!\!\!\!\begin{eqnarray} &&{\rm mod}\ \color{#c0f}4\!:\ 2014^{2013}\ \ \equiv\,\ \ 2^{2013}\equiv\ \ 0\ \ \equiv \color{#0a0}4\\ &&{\rm mod}\ \color{#c0f}5\!:\ 2014^{2013}\equiv (-1)^{2013}\equiv -1\equiv \color{#0a0}4\\\end{eqnarray}\ \Rightarrow\, \color{#0a0}{2014^{2013}\equiv 4\pmod{\color{#c00}{20}}},\ $ by $\,\color{#c00}{20} = {\rm lcm}(\color{#c0f}{4,5})$

${\rm mod}\ 41\!:\ \underbrace{\color{#c00}{2^{20}\equiv 1}}_{\rm given}\,\Rightarrow\,2^{\large \color{#0a0}{2014^{2013}}}\!\equiv 2^{\,\large\color{#0a0}{4+\color{#c00}{20}k}}\equiv 2^{\large 4} (\color{#c00}{2^{\large 20}})^{\large k} \equiv 2^{\large 4} (\color{#c00}1)^{\large k}\equiv 2^{\large 4}\ \ $ QED