Is there a solution for $x^6 \equiv 5 \pmod {71}$?

Question

How can I verify that a solution exists for $$ x^6 \equiv 5 \pmod {71} $$

Answer 1

Edit: since we're asked to prove that a solution exists, we can simply prove that $5$ is both a quadratic residue and a cubic residue mod $71$.

To prove it is a quadratic residue, see the beginning of the other part of my answer (simply use Quadratic Reciprocity).

To prove it is a cubic residue, notice $71$ is a prime of the form $3k+2$.

Theorem: If $p$ is a prime of the form $3k+2$, then every integer is a cubic residue mod $p$.

The proof is short and simple (see Wikipedia).

Lemma: If $p$ is an odd prime and $x^2\equiv y^3\equiv a\pmod{p}$, then $a\equiv z^6\pmod{p}$ for some $z\in\mathbb Z$.

Proof: Let $g$ be a primitive root mod $p$. Then $y\equiv g^t\pmod{p}$ and $x\equiv g^m\pmod{p}$ for some $t,m\in\mathbb Z^+$.

Then $g^{2m}\equiv g^{3t}\pmod{p}$, so $2m\equiv 3t\pmod{p-1}$. Here $p-1$ and $2n$ are both even, so $3t$ is also even, so $t=2h$ for some $h\in\mathbb Z^+$, so $a\equiv \left(g^{h}\right)^6\pmod{p}$.

Therefore $5$ is a six'th power mod $71$.

---

Here's a full solution of the congruence. By Quadratic Reciprocity:

$$\left(\frac{5}{71}\right)=\left(\frac{71}{5}\right)=\left(\frac{1}{5}\right)=1$$

Therefore, by Euler's Criterion:

$$5^{35}\equiv \left(\frac{5}{71}\right)\equiv 1\pmod{71}$$

Therefore:

$$x^6\equiv 5\pmod{71}\iff x^6\equiv \left(5^{12}\right)^3\pmod{71}$$

$$\iff 71\mid \left(x^2-5^{12}\right)\left(x^4+x^2\cdot 5^{12}+5^{24}\right)$$

By Euclid's Lemma either $x^2\equiv 5^{12}\pmod{71}$ or $x^4+x^2\cdot 5^{12}+5^{24}\equiv 0\pmod{71}$.

I.e. either $x\equiv \pm 5^6\equiv \pm 5\pmod{71}$ or $x^4+25x^2+57\equiv 0 \pmod{71}$.

The useful trick in solving quadratic congruences is noticing that if $\gcd(n,4a)=1$, then $$ax^2+bx+c\equiv 0\pmod{p}\stackrel{\cdot 4a}\iff (2ax+b)^2\equiv b^2-4ac\pmod{n}$$

So the last congruence is equivalent to $\left(2x^2+25\right)^2\equiv 42\pmod{71}$.

But by Quadratic Reciprocity:

$$\left(\frac{42}{71}\right)=\left(\frac{2}{71}\right)\left(\frac{3}{71}\right)\left(\frac{7}{71}\right)=(1)\left(-\left(\frac{71}{3}\right)\right)\left(-\left(\frac{71}{7}\right)\right)$$

$$=\left(\frac{2}{3}\right)\left(\frac{1}{7}\right)=(-1)(1)=-1$$

Therefore $x\equiv \pm 5\pmod{71}$ are all the solutions to $x^6\equiv 5\pmod{71}$.

Answer 2

Proposition: $x{^\frac{p-1}{2}} \equiv 1 \pmod p \iff x$ is a square $\pmod p$

Proof: $\impliedby$ obvious. $\implies$ is given by the fact that there are exactly $\frac{p-1}{2}$ squares (not zero) $\pmod p$ and there are at most $\frac{p-1}{2}$ solutions to this equation since $\mathbb Z_p$ is a field.

Given that a solution is $5^6$ because:

$(5^6)^6 \equiv 5^{36} \equiv 5^{35}\cdot 5 \equiv 5 \pmod{71}$.