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

• Yes, you can. Find $y$ such that $2^y \equiv -1 \pmod{59}$. – Daniel Fischer Apr 23 '16 at 15:49

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

• what is with the answer above $$2^{29}\equiv -1 \mod 59$$ this yields the solution $$x=33$$? – Dr. Sonnhard Graubner Apr 23 '16 at 16:01
• @Dr.SonnhardGraubner: In the notation of the answer, we can take $t=29$, so $x=t+4=33$ is a solution. – André Nicolas Apr 23 '16 at 16:04
• Very beautiful answer. +1 – DonAntonio Apr 23 '16 at 16:12
• I don't get the solution to $2^t \equiv -1\pmod{59}$. Could you please elaborate more on that? – Ondrej Sotolar Apr 23 '16 at 16:17
• You may be familiar with Euler's Criterion. If $p$ is an odd prime, then $a^{(p-1)/2}\equiv 1\pmod{p}$ precisely if $a$ is a quadratic residue of $p$, and $a^{(p-1)/2}\equiv -1\pmod{p}$ precisely if $a$ is a quadratic non-residue of $p$. – André Nicolas Apr 23 '16 at 16:30

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.

• How did you come up with the $2^{29}$, did you use the quadratic residue solution? Also I think the modulus should be with $59$. – Ondrej Sotolar Apr 23 '16 at 17:14
• @OndrejSotolar Think of Fermat's Little Theorem. Note that for $2^{58} \equiv 1 \pmod {59}$, we have that if there existed such least $x$ that $2^x \equiv 1 \pmod {59}$, then $x|58$. So since $29$ and $2$ are the only ones. Also, it is not modulo $59$, it's modulo $58$ because $2^{x+59} \not \equiv 2^{x} \pmod {59}$. – S.C.B. Apr 23 '16 at 17:19

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.