# Solving $x^e =c$ in $\mathbb{F}_{p}$

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?

• What do you mean by $\Bbb{F}_{35}$? – Servaes Feb 21 '16 at 1:38
• What is $d$? How does it relate to $e$? – Henno Brandsma Feb 21 '16 at 13:39
• @HennoBrandsma $d$ is any integer such that $d\equiv e^{-1}\pmod{p-1}$. – user236182 Feb 21 '16 at 14:02

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

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

• Nice, well explained answer. – Henno Brandsma Feb 21 '16 at 13:50