Solution to exponential congruence

Solution 1:

We want to solve $2^x\equiv -16\pmod{59}$. Let $x=t+4$. We want to solve $2^t\equiv -1\pmod{59}$.

Note that $2$ is a quadratic non-residue of $59$, because $59$ is not of the shape $8k\pm 1$. Thus $2^{29}\equiv -1\pmod{59}$. That yields the solution $x=33$.

Solution 2:

Somebody posted a very nice solution using quadratic residues, but here is an easier, and slightly more "dirty" solution.

Note that $$2^{29} \equiv (2^6)^{4} \times 32 \equiv 5^4 \times 32 \equiv 35 \times 32 \equiv 7 \times 160 \equiv 7 \times 42 \equiv 294 \equiv -1 \pmod {58}$$ Also note $$2^2 \equiv 4 \pmod {58}$$

This implies that $2$ is a primitive root. Since $$2^{33} \equiv 2^{29} \times 2^{4} \equiv -16 \equiv 43 \pmod {58}$$ We have that $33+58k$ is the only possible solution where $k$ is an integer.