# Remainder in this case using modular arithmetic

How do you find the remainder when $870^{479}$ is divided by 65? My approach:

$870\equiv 25\pmod {65}$

=>$174^{479}\equiv 5^{479}\pmod {13}$

=>$174^{479}\equiv 25^{234.5}\pmod {13}$

Note $\ ca\bmod cn\,=\, c\,(a\bmod n)\$ as we explained here,  hence

\ \, \begin{align} 870^{\large 479}\!\bmod 65\, &=\, 5\,(\color{#0a0}{174}\cdot \color{#c00}{870}^{\large 478}\bmod 13)\\ &=\, 5\,(\ \color{#0a0}5\cdot (\color{#c00}{\bf -1})^{\large 478}\!\bmod 13)\\ &=\, 5\,(\,\color{#0a0}5\,) \end{align}\ \ \ by \ \ \ \begin{align} \color{#0a0}{174}\,&\equiv\,\ \color{#0a0} 5\pmod{13}\\ \color{#c00}{870}\,&\equiv \color{#c00}{\bf -1}\!\!\!\pmod{13}\\ \phantom{.}\end{align}

• @Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. – Bill Dubuque Dec 17 '16 at 4:57

$65=13\times5$

$870^{479}\equiv0 \pmod{5}$

$\color{red}{87}0^{479}\equiv\color{red}{9}0^{479}\equiv(-1)^{479}\equiv-1\pmod{13}$

So $x=870^{479}=-1+13k\equiv0 \pmod 5 \rightarrow k\equiv\frac{1}{13}\equiv\frac 13\equiv\frac63\equiv2 \pmod 5$

and therefore, $x=-1+13\times(2+5k')\equiv-1+26\equiv25 \pmod {65}$

• I could not understand the second and third step. – MrAP Oct 20 '16 at 17:09
• @MrAP He is applying CRT = Chinese Remainder Theorem. I posted an answer that avoids that. – Bill Dubuque Dec 17 '16 at 3:04

HINT: $870^1\equiv870^3\pmod{65}$