Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$? Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$?
 A: Every odd number becomes congruent to $1$ mod $8$ after squaring.
Every odd number becomes congruent to $1$ mod $16$ after being raised to the $4$th power.
...
Every odd number becomes congruent to $1$ mod $64$ after being raised to the $16$th power.
(If $n \geq 3$, then every odd number becomes congruent to $1$ mod $2^n$ after being raised to the $2^{n-2}$nd power.)
Thus if $a$ is odd, $a^{17} \equiv a \bmod 64$.  In particular, $17^{17} \equiv 17 \bmod 64$.
A: A little more concise than Martin Sleziak's solution
$$17^n=(1+16)^n=1+\binom n116+16^2(\cdots)\equiv1+16n\pmod{16^2}$$
$$\implies 17^{17}\equiv1+16\cdot17\equiv1+16(16+1)\pmod{16^2}\equiv17\pmod{16^2}$$
As $64$ divides $16^2,$ $$17^{17}\equiv17\pmod{64}$$
A: $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}$
A: If you have a computer, the easiest thing is to perform 1717 in fixed-precision integer arithmetic and mask off the bottom 6 bits.  You gain no insight into what is going on, but it takes only a few seconds to type in in an appropriate language.  Not bad for easy and fast.  (Scala: Seq.fill(17)(17).product & 63.)
