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.

So this is my question:
Compute $7^{818} \pmod {1637}$ using no more than 14 multiplications mod 1637. (You should of course verify that 1637 is prime if you plan to use Fermat's Theorem.)

I would know how to do this problem if the power that 7 is raised to is higher than 1637. So if I had this:
$$ 2^{200}\pmod{101}$$
I could just do: $2^{100}\equiv 1\pmod{101}$ and go from there to solve. But if I have 1637 then I have to do:
$$7^{1636}\equiv 1\pmod{1637}$$
Then I would have: $$7^{1636}7^{-818}...$$

But I know this is totally wrong. How do I go about this problem?

share|improve this question
2  
You can get from $7$ to $7^{818}$ by a cleverly ordered sequence of steps, each of which consists either of squaring the result of the previous step, or multiplying it by $7$. The binary representation of $818$ is part of the cleverness. Can you see it? –  Gerry Myerson Feb 6 '13 at 6:00
    
@GerryMyerson I think you mean we can do something like $((7^2)^2)^{...}$. But I still don't get how this helps to solve the problem. –  Charlie Yabben Feb 6 '13 at 6:03
    
The problem is to compute $7^{818}$ using no more than $14$ multiplications. So, how many multiplications do you use, doing what I suggested? –  Gerry Myerson Feb 6 '13 at 6:27
add comment

3 Answers 3

up vote 2 down vote accepted
  1. $7^2=7\times 7$
  2. $7^3=7^2\times7$
  3. $7^6=7^3\times7^3$
  4. $7^{12}=7^6\times7^6$
  5. $7^{24}=7^{12}\times7^{12}$
  6. $7^{48}=7^{24}\times7^{24}$
  7. $7^{51}=7^{48}\times7^3$
  8. $7^{102}=7^{51}\times7^{51}$
  9. $7^{204}=7^{102}\times7^{102}$
  10. $7^{408}=7^{204}\times7^{204}$
  11. $7^{816}=7^{408}\times7^{408}$
  12. $7^{818}=7^{816}\times7^2$

It takes at least 12 multiplications to calculate $7^{818}$

share|improve this answer
add comment

Using the binary representation of 818, yields:

$$818_{10} = 1100110010_2$$

There are ones in the $2^{1}, 2^{4}, 2^{5}, 2^{8}, 2^{9}$ positions.

So we can write:

$$7^{818} \pmod {1637} = 7^{(2+16+32+256+512)} \pmod {1637}$$

Using repeated squaring (this hugely reduces your workload), we have:

$$7^{2} \equiv 49 \pmod {1637}$$

$$7^{16} \equiv 899 \pmod {1637}$$

$$7^{32} \equiv 1160 \pmod {1637}$$

$$7^{256} \equiv 765 \pmod {1637}$$

$$7^{512} \equiv 816 \pmod {1637}$$

So, we just multiply these, arriving at

$$7^{818} \pmod {1637} \equiv 49 \cdot 899 \cdot \ 1160 \cdot 765 \cdot 816 \pmod {1637} \equiv 1636 \pmod {1637}$$

Regards

share|improve this answer
    
Excellent demonstration! +1 –  amWhy May 4 '13 at 0:28
add comment

Code in Pari/GP

{powmod(base,expon,modul)=local(a,vb,result,fk,j);
  vb=binary(expon);  \\ a vector containing the binary
                     \\ representation of the exponent
  result=1;
  fk=base;
  j=#vb+1;        \\ supplement index which goes from the tail of
                  \\ vb to its head instead of going like k
  for(k=1,#vb,j--; 
        if(vb[j]==1 ,result = (result * fk) % modul);
        fk =  (fk*fk) % modul
     );
  return(result);}

  \\ test it
powmod(7,818,1637)
 %931 = 1636

powmod(7,818818818818,1637)
 %934 = 1636

powmod(7,100000000000,1637)
 %935 = 908

powmod(7,10^32 ,1637)
 %936 = 379
share|improve this answer
add comment

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.