Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$?
[Math] Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$
elementary-number-theorymodular arithmetic
elementary-number-theorymodular arithmetic
Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$?
Best Answer
$17^4=(16+1)^4=16^4+4\cdot 16^3+6\cdot 16^2+4\cdot 16+1 \equiv 1 \pmod {64}$
(Just notice that all numbers $16^4$, $16^3$, $16^2$ and $4\cdot 16$ are multiples of $64$.)
$17^{17} = (17^4)^4\cdot 17 \equiv 1\cdot 17 \pmod {64}$