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

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?

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

• Thank you :) Why have you chosen mod 20? Aug 23, 2014 at 11:08
• @Artemisia, You have hinted $$2^{10}\equiv-1\pmod{41}\implies2^{20}=(2^{10})^2\equiv?$$ Aug 23, 2014 at 11:09
• OH! Ok I understand now :) Thank you! :) Aug 23, 2014 at 11:10
• @Artemisia, My Pleasure. See also: math.stackexchange.com/questions/905906/… Aug 23, 2014 at 11:11
• @Artemisia Another easy way to compute the exponent E mod $20$ is to compute it mod $4$ and mod $5$ then combine them using CRT, which here is trivial since for both moduli $\,E\equiv 4,\,$ therefore $\,4,5\mid E-4\,\Rightarrow\, 4\cdot 5\mid E-4,\,$ i.e. $\,E\equiv 4\pmod{20}.\,$ See my answer. Aug 23, 2014 at 14:12

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

• This is the perfect one :) thank you :) Sep 1, 2014 at 5:30

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.

• How do you calculate the last ? Aug 23, 2014 at 11:17
• I'd start with (-6)^1 modulo 20, (-6)^2 modulo 20, and so on until I spot a pattern. Aug 23, 2014 at 11:22