So I have a prime $p$, where $p \equiv 2 \pmod{3}$, and $b \not\equiv 0 \pmod{p}$. Given $x\equiv b^{(2p-1)/3} \pmod{p}$, I'm supposed to show that $x^{3} \equiv b \pmod{p}$.

I tried to use Fermat's little theorem for this, but to no avail. I also tried to say something along the lines of

Let $g$ be a primitive root, so that $g^{i} \equiv b$ for some $i$: $$1 \equiv b^{(2p-1)/3} \equiv g^{i(2p-1)/3} \pmod{p}$$ Since the primitive root has order $p-1$, then $p-1 \mid i(2p-1)/3$ and $(p-1)k = i(2p-1)/3$ for some $k$.

From there I was hoping things would simplify nicely, but it doesn’t seem to. I figure I need to show that $i\equiv 0 \pmod{3}$ but I am not sure about doing that.

Apparently when $p \equiv 1 \pmod{3}$, showing that $i \equiv 0 \pmod{3}$ implies that $b$ is a cube mod $p$.

Thanks for any help.


Start by cubing both sides to get:

$$x^3\equiv b^{2p-1} \pmod p$$

Now we can use FLT to get:

$$b^{2p-1}=b^{p-1}\cdot b^{p}\equiv1\cdot b \pmod p$$

EDIT: Note that you will also have to address the special case where $b\equiv 0\pmod p$, but that one is pretty trivial.

  • $\begingroup$ The simple power rules get me every time. Thanks a bunch. $\endgroup$ – probablybadquestions Apr 30 '15 at 8:08
  • $\begingroup$ Maybe mention that $p ≡ 2 \mod 3$ implies that $(2p−1)/3$ is an integer. $\endgroup$ – PM 2Ring Apr 30 '15 at 8:09

Intuitively it is simply $\,x\equiv b^k\!\equiv b^{\color{#0a0}{1/3}}$ $\Rightarrow$ $\,x^3\equiv b,\,$ by $\ k\equiv\color{#0a0}{1/3}\pmod{\!p\!-\!1},\ $ i.e.

$\quad {\rm mod}\,\ p\!-\!1\!:\,\ \color{#c00}{p\equiv 1}\,\Rightarrow\, k = \dfrac{(2\,\color{#c00}p\!-\!1)}3\equiv \dfrac{2\cdot \color{#c00}1-1}3\equiv\color{#0a0}{\dfrac{1}3}\,\ $ so $\,\ b^{\large k}\equiv\, b^{\large\color{#0a0}{ 1/3}}$

Note exponents on $\,b\,$ can be taken $\,{\rm mod}\,\ \color{#c00}{p\!-\!1}\ $ by $\,b^{\large\color{#c00}{p-1}}\equiv 1\pmod p\ $ by

Lemma $\ \ \color{#c00}{b^{\large n} = 1}\ $ and $\ i\equiv j\pmod{n}\ \Rightarrow\ b^{\large i} = b^{\large j}$

Proof $\ \ i = j\! +\! kn\,\Rightarrow\, b^{\large i} = b^{\large j+kn} = b^{\large j}(\color{#c00}{b^{\large n}})^{\large k} = b^{\large j}\color{#c00}1^{\large k} = b^{\large j}$


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.