0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Gerry Myerson Feb 6 '13 at 6:00
  • $\begingroup$ @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. $\endgroup$ – Charlie Yabben Feb 6 '13 at 6:03
  • $\begingroup$ The problem is to compute $7^{818}$ using no more than $14$ multiplications. So, how many multiplications do you use, doing what I suggested? $\endgroup$ – Gerry Myerson Feb 6 '13 at 6:27
2
$\begingroup$
  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}$

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Excellent demonstration! +1 $\endgroup$ – Namaste May 4 '13 at 0:28
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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