Computing Large Powers

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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