Find all solutions to the equation $x^3=7$ in $\mathbb{F}_{13},\mathbb{F}_{19}$ and $\mathbb{F}_{35}$.
In An Introduction to Mathematical Cryptography (Hoffstein et al), we have that proposition 3.2. tells us that if $p$ is a prime and $e \geq 1$ is an integer such that $\gcd(e,p-1)=1$. Then the congruence
$$x^e \equiv c \pmod{p}$$
has the unique solution $x \equiv c^d \pmod{p}$. But in our case we have that in $\gcd (3,12)=\gcd (3,18)=3$ and so this cannot be applied. I accordingly used the brute force method to solve the problem. This gave that $x^3=7$ in $\mathbb{F}_{13}$ has no solutions whereas $x^3=7$ in $\mathbb{F}_{19}$ has three solutions: $x_1=4$, $x_2=6$, and $x_3=9$.
My question is how can I solve this more elegantly?
There are many methods. You already know brute-force, so I won't mention it.
If $x^3\equiv 7\pmod{13}$, then $x^{12}\equiv 7^4\equiv 9\pmod{13}$, but this contradicts Fermat's Little Theorem.
I'll show you two methods for the second problem:
$1)\ \ \ $ $2$ is a primitive root mod $19$ (because $18=2\cdot 3^2$ and $2^{9}\not\equiv 1\pmod{19}$ and $2^{6}\not\equiv 1\pmod{19}$ and by Fermat's Little Theorem $2^{18}\equiv 1\pmod{19}$).
Let $x\equiv 2^k\pmod{19}$. Then $$2^{3k}\equiv 7\equiv 2^6\pmod{19}\iff 3k\equiv 6\pmod{18}$$
$$\iff k\equiv 2\pmod{6}$$
Therefore $2^2,2^8,2^{14}$, i.e. $4, 9, 6$, are all the solutions.
$2)\ \ \ $ Another method: $$x^3\equiv 7\equiv 4^3\pmod{19}\iff 19\mid (x-4)\left(x^2+4x+16\right)$$
By Euclid's Lemma:
$$\iff \begin{cases}19\mid x-4\\\text{or}\\19\mid x^2+4x+16\end{cases}$$
$x\equiv 4\pmod{19}$ is one solution.
$$x^2+4x+16\equiv (x+2)^2+12\equiv 0\pmod{19}$$
$$\iff (x+2)^2\equiv 8^2\pmod{19}$$
$$(x+2)^2-8^2=((x+2)+8)((x+2)-8)=(x+10)(x-6)$$
Again, by Euclid's Lemma: $$\iff \begin{cases}x\equiv -10\equiv 9\pmod{19}\\\text{or}\\x\equiv 6\pmod{19}\end{cases}$$
$$x^3\equiv 7\pmod{35}\iff \begin{cases}x^3\equiv 7\pmod{7}\\x^3\equiv 7\pmod{5}\end{cases}$$
$$\iff \begin{cases}x\equiv 0\pmod{7}\\ x^3\equiv 2\pmod{5}\end{cases}$$
Again, I could use the same two methods on $x^3\equiv 2\pmod{5}$.
There exists exactly one solution here (see the below Theorem).
Here $5$ is small, so it's best to simply use brute-force: checking $0^3,1^3,2^3,3^3,4^3$ mod $5$ only gives that $3^3\equiv 2\pmod{5}$, therefore: $$\iff \begin{cases}x\equiv 0\pmod{7}\\ x\equiv 3\pmod{5}\end{cases}$$
Chinese Remainder Theorem gives the only solution $x\equiv 28\pmod{35}$.
Theorem: if $q$ is a prime of the form $3k+2$, then $x^3\equiv a\pmod{q}$ has exactly one solution (for any $a\in\mathbb Z$).
This is easy to prove: see Wikipedia.