6
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what is with the answer above $$2^{29}\equiv -1 \mod 59$$ this yields the solution $$x=33$$? $\endgroup$ – Dr. Sonnhard Graubner Apr 23 '16 at 16:01
  • 1
    $\begingroup$ @Dr.SonnhardGraubner: In the notation of the answer, we can take $t=29$, so $x=t+4=33$ is a solution. $\endgroup$ – André Nicolas Apr 23 '16 at 16:04
  • 1
    $\begingroup$ Very beautiful answer. +1 $\endgroup$ – DonAntonio Apr 23 '16 at 16:12
  • $\begingroup$ I don't get the solution to $2^t \equiv -1\pmod{59}$. Could you please elaborate more on that? $\endgroup$ – Ondrej Sotolar Apr 23 '16 at 16:17
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Apr 23 '16 at 16:30
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ondrej Sotolar Apr 23 '16 at 17:14
  • $\begingroup$ @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}$. $\endgroup$ – S.C.B. Apr 23 '16 at 17:19
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.