4
$\begingroup$

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?

$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ Thank you :) Why have you chosen mod 20? $\endgroup$
    – Artemisia
    Aug 23, 2014 at 11:08
  • $\begingroup$ @Artemisia, You have hinted $$2^{10}\equiv-1\pmod{41}\implies2^{20}=(2^{10})^2\equiv?$$ $\endgroup$
    – lab bhattacharjee
    Aug 23, 2014 at 11:09
  • $\begingroup$ OH! Ok I understand now :) Thank you! :) $\endgroup$
    – Artemisia
    Aug 23, 2014 at 11:10
  • 1
    $\begingroup$ @Artemisia, My Pleasure. See also: math.stackexchange.com/questions/905906/… $\endgroup$
    – lab bhattacharjee
    Aug 23, 2014 at 11:11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Bill Dubuque
    Aug 23, 2014 at 14:12
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is the perfect one :) thank you :) $\endgroup$
    – Artemisia
    Sep 1, 2014 at 5:30
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .