1
$\begingroup$

$$\large2017^{(2020^{2015})} \pmod{13}$$

I am practicing for my exam and I can solve almost all problem, but this type of problem is very hard to me. In this case, I have to compute this by modulo $13$.

$\endgroup$
  • $\begingroup$ Well you can replace 2017 with 2, did you get that far? $\endgroup$ – Gregory Grant Jan 10 '16 at 14:08
  • $\begingroup$ I did just 2017^2020 mod 13 $\endgroup$ – josf Jan 10 '16 at 14:09
  • $\begingroup$ First off, is this $(2017)^{(2020^{2015})}$? Or is it $(2017^{2020})^{2015}$? $\endgroup$ – Gregory Grant Jan 10 '16 at 14:16
  • $\begingroup$ It is fix now.. $\endgroup$ – josf Jan 10 '16 at 14:23
1
$\begingroup$

As $2017\equiv2\pmod{13},$

$$2017^{2020^{2015}}\equiv2^{2020^{2015}}\pmod{13}$$

Now as $(2020,\phi(13))=4,$ let us find $2020^{2015-1}\pmod{\dfrac{12}4}$

As $2020\equiv1\pmod3\implies2020^{2015-1}\equiv1\pmod3$

$2020^{2015}\equiv2020\cdot1\pmod{3\cdot2020}\equiv2020\pmod{12}\equiv4$

$\implies2^{2020^{2015}}\equiv2^4\pmod{13}=?$

$\endgroup$
0
$\begingroup$

Let's try to see what we can infer from $2017\bmod{13}$:

$2017\equiv\color\red{2}\pmod{13}\implies$

$2017^{6}\equiv\color\red{2}^{6}\equiv\color\green{-1}\pmod{13}\implies$

$2017^{\color\orange{12}}\equiv(2017^6)^2\equiv(\color\green{-1})^2\equiv\color\magenta{1}\pmod{13}$


This means that we can find the answer by representing $2020^{2015}$ as $\color\orange{12}m+n$:

$2017^{2020^{2015}}\equiv2017^{\color\orange{12}m+n}\equiv(2017^{\color\orange{12}})^{m}\cdot2017^{n}\equiv\color\magenta{1}^{m}\cdot\color\red{2}^{n}\pmod{13}$


Let's show by induction that $2020^k\equiv\color\purple{4}\pmod{\color\orange{12}}$:

  • Base case: $2020^1\equiv\color\purple{4}\pmod{\color\orange{12}}$
  • Assumption: $2020^k\equiv\color\purple{4}\pmod{\color\orange{12}}$
  • Inductive step: $2020^{k+1}\equiv2020^k\cdot2020^1\equiv\color\purple{4}\cdot\color\purple{4}\equiv\color\purple{4}\pmod{\color\orange{12}}$

Therefore $2020^{2015}=\color\orange{12}m+\color\purple{4}$, and this gives the final answer:

$2017^{2020^{2015}}\equiv2017^{\color\orange{12}m+\color\purple{4}}\equiv(2017^{\color\orange{12}})^{m}\cdot2017^{\color\purple{4}}\equiv\color\magenta{1}^{m}\cdot\color\red{2}^{\color\purple{4}}\equiv3\pmod{13}$

$\endgroup$
0
$\begingroup$

${\rm mod}\ \color{#c00}{12}\!:\, (\overbrace{4\!+\!12k}^{\large \rm e.g.\ 2020})^{\large 1+n}\!\equiv 4^{\large 1+n}\!\equiv\! \overbrace{4(4^{\large n}\!\bmod 3)}^{\rm\large mod\ Distribute}\!\equiv 4(1^{\large n}\!\bmod 3)\equiv \color{#c00}4,\ $ therefore

${\rm mod}\ 13\!:\,\ a^{\large (4+12k)^{\LARGE 1+n}}\!\equiv a^{\large\color{#c00}{4+12k}}\equiv \underbrace{a^{\large 4}(\color{#0a0}{a^{\large 12}})^{\large k}\!\equiv a^{\large 4} \color{#0a0}{\bf 1}^{\large k}\!}_{\large \rm by\ \color{#0a0}{\rm Fermat}\ \&\ 13\ \nmid\ a}\equiv a^{\large 4},\, $ so $\,{a\equiv 2017\equiv 2}\Rightarrow\,a^{\large 4}\!\equiv 16$

$\endgroup$
  • $\begingroup$ In the first line we used $\ 4b\bmod 4\!\cdot\!3 =\, 4(b\bmod 3 ).\ $ See here on this mod Distributive Law $\endgroup$ – Bill Dubuque Jan 10 '17 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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