Solution to exponential congruence Is there a clever solution to the congruence without going through all the values of x up to 58?$$2^x \equiv 43\pmod{59}$$
Can I somehow use the fact that  $2^4 \equiv -43\pmod{59}$ ?

We know that $2$ is a quadratic non-residue of $59$ from a theorem that states that $2$ is a quadratic residue of $p$, where $p$ is a prime if and only if $\frac{p^2-1}{8}$ is even. Obviously $\frac{59^2-1}{8}$ is odd. 
Also, there is another theorem stating that $a$ is a quadratic residue of $p$ (prime) if and only if $a^{\frac{p-1}{2}} \equiv 1 \pmod p$. Otherwise, $a^{\frac{p-1}{2}} \equiv -1  \pmod p$. (this is known as the Euler's Criterion)
Then, just set $a=2$ and $p=59$ and we have $2^{29} \equiv -1 \pmod{59}$. Therefore $2^4\times2^{29} \equiv(-43)(-1) \equiv 43 \pmod {59}$ i.e. $2^{33} \equiv 43 \pmod{59}$.
Are we done yet? Nop!
We want to find every such $x$.
Let y be another solution. Then:
$43 \times 2^{y-33} \equiv 2^{33} \times 2^{y-33} \equiv 2^{y} \equiv 43 \pmod{59}$. Note that this works even if $y$ is smaller than $33$ -there is no such solution but there is no need to prove it.
So by cancelation  ($\gcd(43,59)=1$ so we can do this) we end up with $2^{y-33} \equiv 1 \pmod{59}$. $(1)$
There is another known result, stating that the minimum solution of the equation  $a^x \equiv 1 \pmod{n}$ for some $a,n$ in positive integers divides all the others. Let $d$ be the minimum solution of $2^z \equiv 1 \pmod{43}$.
Also, by Fermat Little Theorem $2^{58} \equiv 1 \pmod{59}$. By the result mentioned before, $z|58=2\times29$. Since $2^1\equiv 1 \pmod{59}$, $2^2 \equiv 4 \pmod{59}$ and $2^{29} \equiv -1 \pmod{59}$ (proved before), we have $z=58$.
Note also that from $(1)$ we have that $y$ is a solution of our equation if and only if $58|y-33$.
Therefore, the solutions are given by $x=33+58t$ where $t$ is an integer.
