Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
...you have seen this, no? –  J. M. Nov 27 '11 at 12:45
    
Remainder ---> 17 –  Felix Marin Dec 24 '13 at 8:51

4 Answers 4

up vote 2 down vote accepted

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

share|improve this 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}$

share|improve this answer
1  
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$.

share|improve this answer

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.