# 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}$ ?

#### Solutions Collecting From Web of "Solution to exponential congruence"

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

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.

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.