# Computing Large Powers

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

-
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

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

-

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

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

-
Excellent demonstration! +1 –  amWhy May 4 '13 at 0:28

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

-