Intereting Posts

$f(0)=f'(0)=f'(1)=0$ and $f(1)=1$ implies $\max|f''|\geq 4$
Given an injection $\mathbb{N}\to\mathcal{P}(X)$, how can we construct a surjection $X\to\mathbb{N}$?
Outer measure is countably subadditive
General solution to a system of non linear equations with a specific pattern
Deriving the formula for the $n^{th}$ tetrahedral number
How to prove that this set is closed?
show $\lim_{x\to 0}\frac{e^x-1}{x}=1$ without L'Hopital
Prove $f: X \rightarrow Y$ is continuous if $A_a$ is closed and $f|A_a$ is continuous for any $a$ and $\text{{$A_a$}}$ is locally finite collection
Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.
Find a positive integer such that half of it is a square,a third of it is a cube,and a fifth of it is a fifth power
Why does this infinite series equal one?
$E$ Lebesgue measurable implies $E^2$ Lebesgue measurable?
Yet another $\sum = \pi$. Need to prove.
Does there exist a continuous function from to R that has uncountably many local maxima?
About Mellin transform and harmonic series

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

- Find two numbers whose sum is 20 and LCM is 24
- Find all solutions to $x^3+(x+1)^3+ \dots + (x+15)^3=y^3$
- Is greatest common divisor of two numbers really their smallest linear combination?
- find a parametric solutions for a special equation
- If $x^2+ax+b=0$ has a rational root, show that it is in fact an integer
- On the factorial equations $A! B! =C!$ and $A!B!C! = D!$
- Can an odd perfect number be a nontrivial multiple of a triangular number?
- Compositeness of $n^4+4^n$
- Find the sum of reciprocals of divisors given the sum of divisors
- Any digit written $6k$ times forms a number divisible by $13$

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.

- Solving recurrence relation?
- Why does $\arctan(x)= \frac{1}{2i}\log \left( \frac{x-i}{x+i}\right)+k$?
- Higher dimensional analogues of the argument principle?
- Closed form for the limit of the iterated sequence $a_{n+1}=\frac{\sqrt{(a_n+b_n)(a_n+c_n)}}{2}$
- $e$ as the limit of a sequence
- Derivation of the quadratic equation
- Showing that no Hamilton Circuit exists
- Why is $D^n/\sim$ homeomorphic to $\mathbb{RP}^n$?
- Decomposition into partial fractions of an inverse of a generic polynomial with three distinct roots.
- Is it always true that $\det(A^2+B^2)\geq0$?
- Every point of an open ball is a centre for the open ball.
- Monoid as a single object category
- Number of colorings of cube's faces
- Calculating derivative by definition vs not by definition
- solve a trigonometric equation $\sqrt{3} \sin(x)-\cos(x)=\sqrt{2}$