1
$\begingroup$

Solve $[2^{(2^{403})}] = [a]$ in $\mathbb Z_{23}$ where $0 \le a < 23$.

I've tried to combine corollaries of Fermat's little theorem and various other methods to solve this, but have always been stuck.

$\endgroup$
1
$\begingroup$

Well, the order of $2$ modulo $23$ is $11$ (you can verify this). So, look at $2^{403}$ modulo $11.$

You will find the order of $2$ modulo $11$ to be $10$. This implies $$2^{403} \equiv 2^{10 \cdot 40+3} \equiv 2^3 \equiv 8 \text{mod}(23).$$

Thus, $$2^{2^{403}} \equiv 2^8 \equiv (2^5)(2^2)2 \equiv (9 \cdot 4) \cdot 2 \equiv 13 \cdot 2 \equiv 26 \equiv 3 \text{mod}(23).$$

$\endgroup$
  • 1
    $\begingroup$ $$2^8=256\equiv3\pmod{23}$$ $\endgroup$ – lab bhattacharjee Nov 12 '17 at 1:25
  • $\begingroup$ @labbhattacharjee indeed. I just couldn’t see that immediately and so I broke I️t down in a way that I could get I️t quickly. $\endgroup$ – user328442 Nov 12 '17 at 1:26
0
$\begingroup$

Here's a way you could do it without orders of modulo...just in case you haven't learned it yet ;)

You can look at 2^403 modulo 22 (Splitting the modulus will make life easier). You'll get some equation involving 22 and you'll be able to use Fermat's little theorem.

Edit: on my phone, not sure how to format numbers

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