# 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$?

-
...you have seen this, no? –  Ｊ. Ｍ. Nov 27 '11 at 12:45
Remainder ---> 17 –  Felix Marin Dec 24 '13 at 8:51

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

-

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

-
The choice of 4 as the exponent is just to make things easy for the rest of the calculation right? –  Quixotic Nov 27 '11 at 12:48
Right. Basically it's a guesswork, but in this particular case it's easy to notice. –  Martin Sleziak Nov 27 '11 at 12:49

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

-

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.)

-
The easiest thing to do is this. –  Quixotic Nov 27 '11 at 18:58
...and Wolfram Alpha can certainly do PowerMod[17, 17, 64]... –  Ｊ. Ｍ. Nov 28 '11 at 12:34
There are many appropriate languages, obviously. –  Rex Kerr Nov 28 '11 at 14:09