1
$\begingroup$

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?

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

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.

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

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.