4
$\begingroup$

Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$?

  • 4
    ...you have seen [this](http://math.stackexchange.com/questions/81228), no?2011-11-27
  • 0
    Remainder ---> 172013-12-24

4 Answers 4

0

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

  • 0
    The easiest thing to do is [this](http://ideone.com/o0yVm).2011-11-27
  • 1
    ...and Wolfram Alpha can certainly do `PowerMod[17, 17, 64]`...2011-11-28
  • 0
    There are many appropriate languages, obviously.2011-11-28
17

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

  • 1
    The choice of 4 as the exponent is just to make things easy for the rest of the calculation right?2011-11-27
  • 0
    Right. Basically it's a guesswork, but in this particular case it's easy to notice.2011-11-27
6

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

2

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