# Modular arithmetic problem (mod $13$)

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

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

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

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

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

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