6
$\begingroup$

Prove that $x^3 \equiv a \pmod{p}$ has a solution where $p \equiv 2 \pmod{3}$?

How can I prove a congruence equation has a solution? I tried to link Fermat's little theorem with this problem, but I couldn't find a way to solve it.

My attempt was: $$x^3 \equiv 1 \pmod{2}$$ $$x^3 \equiv a \pmod{p}$$

If $p \equiv 2 \pmod{3}$, I have $p = 3k + 2$, for some integers $k$. But I was stuck here :(. Any idea?

Another question is, is there are infinitely many primes of the form 3k + 2? A hint would be sufficient.

Thanks, Thanks,

$\endgroup$
6
  • $\begingroup$ You are not asked to show it has a solution, you are asked to show it has at most one solution; that is, either no solutions, or one solution. $\endgroup$ Mar 16, 2011 at 4:16
  • 2
    $\begingroup$ Yes; there are infinitely many primes of the form $3k+2$. In general, there are infinitely many primes of the form $ak+b$ whenever $\gcd(a,b)=1$. Look up "Dirichlet's theorem on primes in arithmetic progressions." $\endgroup$ Mar 16, 2011 at 4:17
  • $\begingroup$ @Arturo Magidin: Thanks. It should be has a solution, and at most. $\endgroup$
    – roxrook
    Mar 16, 2011 at 4:51
  • $\begingroup$ +1 for showing some effort. But $5^3=1^3 \pmod {62}$ so you need to specify that $p$ is prime. Similarly, $11^3=1 \pmod{35}$ and $\pmod {38}$. Focusing on $11^3=1 \pmod{35}, 11^3=4^3=1 \pmod{7}$, while $11=1 \pmod {5}$, so $11^3=1 \pmod{5}$. It seems you need $p$ prime so you can't factor it into something $=2 \pmod {3}$ and something $=1 \pmod {3}$ (which might have two solutions) $\endgroup$ Mar 16, 2011 at 5:02
  • $\begingroup$ @Ross Millikan: Thanks a lot. I will think a bit more. $\endgroup$
    – roxrook
    Mar 16, 2011 at 5:39

4 Answers 4

7
$\begingroup$

Hint $\:$ Show $ \: x\to x^3\: $ is a bijection via $\rm\color{#c00}{little\ Fermat}$ and $\, \overbrace{3 (2K\!+\!1) = 1 + 2(3K\!+\!1)}^{\textstyle 3J\ \equiv\ 1\ \pmod{p-1}}$

In detail: $ \ \ x^{3J} =(x^{\color{#0a0}{2K+1}})^{\large 3}=\ x (\color{#c00}{x^{3K+1}})^{\large 2} \equiv x\pmod{\!p}\ \ $ for $ \ x\not\equiv 0,\, $ prime $\,p = 3K\!+\!2$.

Thus $ \ x\to x^3\ $ is onto on the finite set $ \:\mathbb Z/p\:,\:$ so it is also $\,1$-$1,\,$ i.e. $ \ x^3 \equiv y^3\, \Rightarrow\, x\equiv y$.

Note: this answers the original version of your question (existence and uniqueness of cube roots).

Remark $ $ the exponent $\,J = \color{#0a0}{2K\!+\!1}$ with $\,x^{3J}\equiv x^{\large 1}\pmod{p=3K\!+\!2}\,$ was computed via

$\!\bmod p\!-\!1=3K\!+\!1\!:\ \ 3J\equiv 1\iff J\equiv \dfrac{1}{3}\equiv \dfrac{-3K}3\equiv -K\equiv \color{#0a0}{2K+1}$

using modular order reduction and $\bmod p\!:\ x^{\large p-1}\equiv 1,\ x\not\equiv 0,\,$ by little Fermat.

$\endgroup$
2
  • $\begingroup$ Thanks, but I really don't know what's a bijection :(. $\endgroup$
    – roxrook
    Mar 16, 2011 at 4:51
  • $\begingroup$ @Chan: A bijection is a function $f:X \rightarrow Y$ which is both injective (no two $x's \in X$ map to the same $y \in Y$), and surjective (for every $y \in Y$, we can find an $x \in X$ such that $f(x) = y$). Some knowledge of elementary ring theory (particularly familiarity with the ring $\mathbb{Z}_p$ would be very helpful for this problem, so might be worth looking up. $\endgroup$ Mar 16, 2011 at 5:04
5
$\begingroup$

For reference, check out Ireland and Rosen's A Classical Introduction to Modern Number Theory, which will allow you a first taste on a bunch of topics in number theory (though the authors assume basic familiarity with abstract algebra). What's nice about your question is that it admits several methods of proof.

Notice that your hypothesis on $p$ is unnecessary if $a \equiv 0 \pmod{p}$ (simply use $x=0$). So assume $a \not\equiv 0 \pmod{p}$. In that case, Ch.4 of Ireland and Rosen tells us that (1) $a^{p-1} \equiv 1 \pmod{p}$ and (2) $x^3 \equiv a \pmod{p}$ is solvable if and only if $$a^{(p-1)/\gcd(p-1, 3)} \equiv 1 \pmod{p}.$$ But guess what: since $p-1 \equiv 1 \pmod{3}$ by hypothesis, congruence theory says $$\gcd(p-1, 3) = \gcd(1, 3) = 1.$$ Thus by (1), $$a^{(p-1)/\gcd(p-1, 3)} = a^{p-1} \equiv 1 \pmod{p},$$ and so we're done!

$\endgroup$
3
$\begingroup$

My intuition tells me to attempt a proof by contradiction via factoring: Assume $x^3 \equiv y^3 \equiv a \pmod p$ thus $(x-y)(x^2+xy+y^2) = x^3-y^3 \equiv 0$. Since $\mathbb{Z}_p$ is an integral domain and we are assuming $x$ and $y$ are distinct (as elements of $\mathbb{Z}_p$, we must have $x^2+xy+y^2 \equiv 0$, thus $x^2+xy+y^2 = n(3k+2)$ for some $n$. If $n$ is even we have that every term is even, which allows us to factor out $2$ from $x$ and $y$. We can assume this is true since if $x$ is an odd solution, $x+3k+2$ is an even solution as operations on $\mathbb{Z}_p$ are well-defined, and similarly for $y$. Thus we have $x/2$ or $(x+3k+2)/2$ and $y/2$ or $(y+3k+2)/2$ are solutions. You should be able to derive a contradiction from there.

$\endgroup$
1
  • $\begingroup$ Thank you. Your approach is very interesting, and suit my elementary level ;). $\endgroup$
    – roxrook
    Mar 16, 2011 at 5:40
3
$\begingroup$

You can verify directly, using Fermat's little theorem, that $x=a^{(2p-1)/3}$ is a solution to $x^3\equiv a\pmod p$ (and $(2p-1)/3$ is an integer since $p\equiv2\pmod 3$).

(Coming up with this solution is not quite as easy as verifying it, to be sure. Because of the existence of a primitive root $g$ modulo $p$, proving that $x^3\equiv a\pmod p$ always has a solution is equivalent, thanks to the change of variables $a = g^c$ and $x=g^b$, to proving that $3b \equiv c \pmod{p-1}$ always has a solution. This latter congruence has the solution $b\equiv 3^{-1}c = \frac{2p-1}3 c\pmod {p-1}$. Here the case $a\equiv0\pmod p$ should be treated separately.)

There are infinitely many primes of the form $3k+2$, that is, infinitely many primes that are congruent to $2\pmod 3$. See Dirichlet's theorem or the prime number theorem for arithmetic progressions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .