Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
    
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. –  Arturo Magidin Mar 16 '11 at 4:16
2  
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." –  Arturo Magidin Mar 16 '11 at 4:17
    
@Arturo Magidin: Thanks. It should be has a solution, and at most. –  Chan Mar 16 '11 at 4:51
    
+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) –  Ross Millikan Mar 16 '11 at 5:02
    
@Ross Millikan: Thanks a lot. I will think a bit more. –  Chan Mar 16 '11 at 5:39

4 Answers 4

up vote 5 down vote accepted

HINT $\:$ Show $\rm\: x\to x^3\: $ is a bijection using Fermat's little theorem and $\rm\: 3\ (2\:K+1) = 1 + 2\ (3\:K+1)$

In further detail: $\rm\ \ (x^{2\:K+1})^3\ =\ x\ (x^{3\:K+1})^2\ \equiv\ x\ \ (mod\ P)\ \ $ for $\rm\ x\not\equiv 0\:,\ $ prime $\rm\ P = 3\:K+2\:.$

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

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

share|improve this answer
    
Thanks, but I really don't know what's a bijection :(. –  Chan Mar 16 '11 at 4:51
    
@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. –  Alex Becker Mar 16 '11 at 5:04

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!

share|improve this answer

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.

share|improve this answer
    
Thank you. Your approach is very interesting, and suit my elementary level ;). –  Chan Mar 16 '11 at 5:40

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.