0
$\begingroup$

Let $p$ be a prime and $p \geq 5$, Consider the congruence $x^3 \equiv a$ (mod p) with $\gcd(a,p)=1$. Show that The congruence has either no solution or three incongruent solutions modulo $p$ if $p \equiv 1$ (mod 6) and has unique solution modulo $p$ if $p \equiv 5$ (mod 6).

My attempt: By Lagrange theorem, the congruence $x^3 \equiv a$ (mod p) has at most $3$ incongruent solutions modulo $p$. Suppose the congruence has a solution $b$ such that $b^3 \equiv a$ (mod p). Then $x^3 \equiv a \equiv b^3 \textit{mod p} \Rightarrow x^3 -b^3 \equiv 0$ (mod p). Note that $x^3 -b^3=(x-b)(x^2+bx+b^2)$

Now I stuck at here. I observe that if $p \equiv 1$ (mod 6), then $(x^2+bx+b^2) \equiv 0$ (mod p) has two incongruent solutions modulo $p$ and if $p \equiv 5$ (mod 6), then $(x^2+bx+b^2) \equiv 0$ (mod p) has one unique solution modulo $p$.

Can anyone guide me?

$\endgroup$
  • $\begingroup$ Wait, how can $p$ be congruent to $1(\mod\ p)$? $\endgroup$ – abiessu Sep 21 '13 at 15:51
  • $\begingroup$ Sorry, typo. It should be modulo $6$ $\endgroup$ – Idonknow Sep 21 '13 at 16:09
  • $\begingroup$ @Idonknow, please complete the first line "Consider the congruence $x^3 \equiv$ (mod p) " $x^3\equiv?\pmod p$ $\endgroup$ – lab bhattacharjee Sep 21 '13 at 16:54
3
$\begingroup$

We give an extremely detailed argument. Sorry about the length!


Suppose first that $p\equiv 1\pmod{6}$. So $p=6k+1$ for some $k$.

We will use a primitive root argument. Let $g$ be a primitive root of $p$. In group-theoretic terms, let $g$ be a generator of the multiplicative group modulo $p$.

Then $g$ has order $p-1$ modulo $p$. Note that $g^{p-1}=(g^{2k})^3\equiv 1\pmod{p}$ by Fermat's Theorem. Also, $(g^{4k})^3\equiv 1\pmod{p}$. Neither $g^{2k}$ nor $g^{4k}$ is congruent to $1$ modulo $p$, since the order of $g$ is $6k$. And they are not congruent to each other.

Thus the congruence $z^3\equiv 1\pmod{p}$ has at least $3$ (and therefore exactly $3$ solutions, namely $1$, $g^{2k}$, and $g^{4k}$.

So if $b^3\equiv a\pmod{p}$, then we also have $(g^{2k}b)^3\equiv a\pmod{p}$ and $(g^{4k}b)^3\equiv a\pmod{p}$. It follows that the congruence $x^3\equiv a \pmod{p}$ has $3$ solutions if it has a solution.


Now suppose that $p\equiv 5\pmod{6}$. Let $p=6k+5$. Let $x$ and $y$ be non-zero integers, and suppose that $x^3\equiv y^3\pmod{p}$. This is the case if and only if $(xy^{-1})^3\equiv 1\pmod{p}$. We show that this forces $x\equiv y\pmod{p}$.

To do this, it is enough to show that the congruence $z^3\equiv 1\pmod{p}$ has only the obvious solution $z\equiv 1\pmod{p}$.

Again let $g$ be a primitive root of $p$. Any $z$ is congruent to $g^m$ for some $m$ with $1\le m\le p-1$. Ig $z^3\equiv 1\pmod{p}$ then $g^{3m}\equiv 1\pmod{p}$. It follows that $3m$ divides the order of $g$, that is, $3m$ divides $6k+4$. Since $3$ and $6k+4$ are relatively prime, it follows that $m$ divides $6k+4=p-1$. Thus $g^m\equiv 1\pmod p$, and therefore $z\equiv 1\pmod{p}$.

Now consider the mapping $\psi$ that takes any number $x$ between $1$ and $p-1$ into the remainder when $x^3$ is divided by $p$. By the calculation above, the function is one to one (injective). A one to one function from a finite set to itself must be onto (surjective). It follows that every number between $1$ and $p-1$ is $\psi(x)$ for some $x$. This says that every number between $1$ and $p-1$ is congruent to $1$ modulo $p$. That is what we wanted to prove.

$\endgroup$
0
$\begingroup$

As $p \neq 2$ you know that $2$ is invertible modulo $p$. Let $\alpha$ be its inverse.

By completing the square we get

$$(x^2+bx+b^2) \equiv 0 \Rightarrow x^2+bx+\alpha^2 b^2 \equiv \beta^2(\alpha^2-1) \equiv \beta^2 \alpha^2 (1-4) \pmod{p}$$

Now all you have to do is study if $-3$ is a quadratic residue modulo $p$. The fact that you have to look at $p \mod 6$ comes very natural from here:

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

Simpler solution Note that $b \neq 0 \pmod{p}$. Then

$$x^3 \equiv b^3 \pmod{p} \Leftrightarrow (xb^{-1})^3 \equiv 1 \pmod{p}$$

Now, if $p \equiv 1 \pmod{6}$, once you prove that $y^3 \equiv 1 \pmod{p}$ has three solutions, the conclusion follows immediately.

If $p \equiv 5 \pmod{6}$, you can prove that $y^3 \equiv 1 \pmod{p}$ has unique solution. From here, it follows immediately that $x^3 \equiv b^3 \pmod{p} \Rightarrow x \equiv b \pmod{p}$. Thus, the function $f (x)= x^3$ is an one to one function $\mod{p}$, hence a bijection.

$\endgroup$
0
$\begingroup$

$$x^3\equiv a\pmod p\ \ \ \ (1)$$

Taking Discrete logarithm, wrt some primitive root $g\pmod p$ as we can prove that every prime has at least one primitive root

$3\cdot\text{ind}_gx\equiv \text{ind}_ga\pmod {p-1}\ \ \ \ (2)$

Using Linear congruence theorem, $(2),$ hence $(1)$ will be solvable if $(3,p-1)|\text{ind}_ga$

If $p=6b+5,$ where integer $b\ge0$ $\implies (3,p-1)=(3,6b+5)=(3,6b+5-3(2b+1))=(3,2)=1$

$\displaystyle (3,p)=1$ will always divide $\text{ind}_ga\forall a$ and consequently from the Linear congruence theorem, we have $(3,p)=1$ solution $\forall a$

If $p=6b+1,$ where integer $b\ge0 \implies(3,p-1)=(3,6b)=3$

$(2),$ hence $(1)$ will be solvable if $(3,p-1)=3|\text{ind}_ga$

If so, from the Linear congruence theorem, we have $(3,p)=3$ solutions if $3|\text{ind}_ga$

$\endgroup$

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.