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$?
-
0Remainder ---> 17 – 2013-12-24
4 Answers
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
.)
-
0There are many appropriate languages, obviously. – 2011-11-28
$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}$
-
0Right. Basically it's a guesswork, but in this particular case it's easy to notice. – 2011-11-27
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 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}$