0
$\begingroup$

I have had a go at this for a while now and can't seem to get anywhere.

$$2^{(2^{517})} \pmod {23}$$

I see that Fermat's Little Theorem must come into play but I can't see where to pull $22$ from. Any help would be appreciated.

Here is my attempt:

$$2^{(2^{517} \!\!\mod {22})} \equiv 2^{(2^{517})} \pmod {23}$$ Then proceed to do Chinese remainder theorem to find the exponent?

$\endgroup$
  • 2
    $\begingroup$ Take $2^{517}$ mod $22$ as your new exponent $\endgroup$ – TokenToucan Mar 14 '16 at 3:44
2
$\begingroup$

Note that $2^{11}=2048\equiv1\pmod{23}$

Next note that: $2^{10}=1024\equiv1\pmod{11}$

So $2^{2^{517}}\equiv2^{2^7}\pmod{23}$ as $2^{517}\equiv2^7\pmod{11}$

Hence $2^{2^{517}}\equiv2^{128}\pmod{23}\equiv2^7\pmod{23}=128\equiv13\pmod{23}$

$\endgroup$
  • $\begingroup$ is there a reason for the switch from 517 to 57? $\endgroup$ – softie Mar 14 '16 at 4:10
  • $\begingroup$ A typo. I accidiently missed the 1. It doesn't change the working. Fixed now. $\endgroup$ – Ian Miller Mar 14 '16 at 9:45

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.