If $2^{12^{7}+3}\equiv x \pmod{36}$, then what is the value of $x$?

Question

If $2^{12^{7} + 3} \equiv x \pmod{36}$, then what is the value of $x$?

We have:

$$ \begin{align} 2^5 & \equiv - 4 \pmod{36} \\ 2^{10} & \equiv 16 \pmod{36} \\ 2^{12} & \equiv - 8 \pmod{36} \\ (2^{12})^{12} & \equiv 8^{12} \pmod{36} \\ 2^{12^2} & \equiv - 8 \pmod{36} \text{, as } 8^{12} \equiv - 8 \pmod{36} \\ (2^{12^2})^{12^5} & \equiv - 8 \pmod{36} \\ 2^{12^7} & \equiv - 8 \pmod{36} \\ 2^{{12^7} + 3} & \equiv - 64 \pmod{36} \\ 2^{{12^7} + 3} & \equiv 8 \pmod{36} \\ \end{align} $$

Am I right or wrong? Is there any simpler way to find it?

Answer 1

It's probably easier to work modulo $4$ and modulo $9$, and use CRT.

First we have $$x \equiv 2^{12^{7}+3}\equiv 0 \pmod{4}$$

To compute $$x \equiv 2^{12^{7}+3} \pmod{9},$$ it suffices to compute $12^{7} + 3 \equiv 3 \pmod{6}$, as $6 = \varphi(9)$. (Or, if you prefer, as $2^{6} \equiv 1 \pmod{9}$.) So $$2^{12^{7}+3}\equiv 2^{3} \equiv 8 \pmod{9}.$$

Clearly, then, the solution is indeed $x = 8$ as you found it, as $8 \equiv 0 \pmod{4}$.

Answer 2

We need $x \in \{0,1,2,\ldots,35\}$ such that $2^{12^7+3} = 36M + x$. Note that $4$ divides $2^{12^7+3}$ and $36M$. Hence, $x$ must be a multiple of $4$, say $4y$. We now need $y$ such that $$2^{12^7+1} = 9M + y$$ where $y \in \{0,1,2,\ldots,8\}$. Since $\gcd(2,9) = 1$, we have $$2^{\phi(9)} \equiv 1 \pmod9 \implies 2^6 \equiv 1\pmod9$$ We have $12^7+1 = 6t+1$. Hence, $$2^{12^7} \equiv 1 \pmod9 \implies 2^{12^7+1} \equiv 2 \pmod9$$ Hence, $y=2$, which gives us that $x=8$.