Exercise 9.41

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Let $p\equiv 1 \pmod 6, 4p = A^2 + 27 B^2, A \equiv 1 \pmod 3$, $A$ and $B$ odd. Put $\pi = a+b\omega, 2a-b =A, b = 3B$. Let $\chi_\pi$ be the cubic residue character.
\begin{enumerate}
\item[(a)] If $\chi_\pi(2) = \omega$ show $N(x^3+2y^3 = 1) = p+1 + 2b-a \equiv 0 \pmod 2$.
\item[(b)] If $\chi_\pi(2) = \omega^2$ show $N(x^3 + 2y^3 = 1) = p+1 -a-b \equiv 0 \pmod 2$.
\item[(c)] Show that if $A \equiv B \pmod 4$, then assuming $\chi_\pi(2) 
e 1$, one has $\chi_\pi(2) = \omega$.
\item[(d)] If $\chi_\pi(2) 
e 1, A \equiv B \pmod 4$ then $$2^{(p-1)/3} \equiv (-A-3B)/6B \equiv (A+9B)/(A-9B) \pmod \pi.$$

(This generalization of Euler's criterion is due to E.Lehmer [174]. See also K.Williams [243].)
\end{enumerate}

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof}
With the help of Theorem 1, Chapter 8, we obtain, writing $\chi_\pi(2) = \omega^k$,
\begin{align*}
N(x^3 + 2 y^3 = 1)&= \sum_{a+2b = 1} N(x^3 =a) N(y^3 = b)\
&=\sum_{a+2b = 1} \left(\sum_{i=0}^2 \chi_\pi^i(a)ight)\left( \sum_{j=0}^2 \chi_\pi^j(b)ight)\
&=\sum_{i=0}^2\sum_{j=0}^2 \sum_{a+2b=1} \chi_\pi^i(a)\chi_\pi^j(b)\
&=\sum_{i=0}^2\sum_{j=0}^2  \sum_{a+b' = 1} \chi_\pi^i(a) \chi_\pi^j(2^{-1} b')\
&=\sum_{i=0}^2\sum_{j=0}^2 \chi_\pi(2)^{-j} J(\chi_\pi^i, \chi_\pi^j)\
&=\sum_{i=0}^2\sum_{j=0}^2 \omega^{-kj} J(\chi_\pi^i, \chi_\pi^j)\
&= p + \omega^{-k} J(\chi_\pi^2,\chi_\pi) + \omega^{-2k} J(\chi_\pi,\chi_\pi^2)\
&\phantom{= p .} + \omega^{-k} J(\chi_\pi, \chi_\pi) + \omega^{-2k} J(\chi_\pi^2, \chi_\pi^2)\
&=p - \omega^{-k} \chi_\pi(-1) - \omega^{-2k} \chi_\pi^2(-1) + 2 e(\omega^{-k} J(\chi_\pi,\chi_\pi)\
&= p - \omega^{-k} -  \omega^{-2k} +  2 e(\omega^{-k} J(\chi_\pi,\chi_\pi)).
\end{align*}

\begin{enumerate}

\item[(a)] If $\chi_\pi(2) = \omega$, then $k=1$. Using $\chi_\pi^2 = \chi_\pi^{-1} =\overline{\chi_\pi}$, we obtain
\begin{align*}
N(x^3 + 2 y^3 = 1)&= p+1+ 2 e(\omega^{2} J(\chi_\pi,\chi_\pi))\
&=p+1 + 2 e(\omega^2 \pi),
\end{align*}
since $J(\chi_\pi,\chi_\pi) = \pi$ (Lemma 1, section 4).
\begin{align*}
\omega^2\pi &= \omega^2(a + b \omega) = b - a -\omega a,\
2 e(\omega^2\pi) &= (b-a -\omega a) + (b - a - \omega^2 a) = 2b-2a + a = 2b-a,
\end{align*}
therefore
$$N(x^3 + 2 y^3 = 1) = p+1 + 2b -a\qquad (	ext{if }\chi_\pi(2) = \omega).$$
Since case is $\chi_\pi(2) = \omega$, then $a \equiv 0 \pmod 2$ (see Ex. 40, part (e)), so $p + 1 + 2b -a \equiv 0 \pmod 2$.

(b) If $\chi_\pi(2) = \omega^2 = \omega^{-1}$, then $k=-1$, and
\begin{align*}
N(x^3 + 2 y^3 = 1)&= p+1+ 2 e(\omega \pi),\
\end{align*}
with 
\begin{align*}
\omega \pi &= \omega (a + b \omega) = -b + (a-b)\omega,\
2 e(\omega \pi) &= (-b + (a-b) \omega) +( -b + (a-b)\omega^2) = -2b - (a-b) = -a -b,
\end{align*}
therefore
$$N(x^3 + 2y^3 = 1) = p+1 -a-b \qquad (	ext {if }\chi_\pi(2) = \omega^2).$$
Since case is $\chi_\pi(2) = \omega^2$, then $a \equiv 1 \equiv b \pmod 2$ (see Ex. 40, part (e)), so $p + 1 -a -b\equiv 0 \pmod 2$.

\item[(c)] Suppose that $A\equiv B \pmod 4$, and $\chi_\pi(2)
e 1$. By hypothesis, $b = 3B$, and this implies by Exercise 40 (e) that $\chi_\pi(2) = \omega$ (if not, $\chi_\pi(2) = \omega^2$, and $A\equiv B \pmod 4$ gives $B = -b/3$).

\item[(d)] Suppose that $\chi_\pi(2) 
e 1, A\equiv B \pmod 4$. By part (c), $\chi_\pi(2) = \omega$.

Since $2a-b = A, B = b/3$, then $a = \frac{A+3B}{2}, b = 3B$.

Starting from $a + b \omega \equiv 0 \pmod \pi$, we obtain
$$ 3B \omega \equiv -\frac{A+3B}{2} \pmod \pi.$$
Since $p = a^2 - ab + b^2$, $a$ is relatively prime with $p$, therefore $\pi \wedge b = 1$, so $\pi \wedge B = 1$, and $\pi \wedge 6 = 1$, since $p \equiv 1 \pmod 6$, thus
$$\chi_\pi(2)  = \omega \equiv \frac{-A-3B}{6B} \pmod \pi,$$
where we must read in this fraction the product of $A + 3B$ by the inverse modulo $p$ of $6B$.
By definition, using $N(\pi) = p$, 
$$\chi_\pi(2) \equiv 2^{\frac{p-1}{3}} \pmod \pi,$$
so
$$2^{\frac{p-1}{3}} \equiv \frac{-A-3B}{6B}  \pmod \pi.$$

Moreover, since  $4p = A^2 + 27 B^2$, $A^2 + 27 B^2 \equiv 0 \pmod p$, therefore
$$ 6B(A+9B) + (A+3B)(A-9B) \equiv 0 \pmod p.$$
If $p \mid A-9B$, since $p 
mid 6B$, this equality implies that $p\mid A+9B$, therefore $p \mid (A-9B) + (A+9B) = 2A$, which is false. Therefore $A-9B 
ot \equiv 0 \pmod p$, and
$$2^{\frac{p-1}{3}} \equiv \frac{-A-3B}{6B}  \equiv \frac{A+9B}{A-9B} \pmod \pi.$$
\end{enumerate}

\end{proof}

Note : By a usual argument, if $h \in \Z$, $2^{\frac{p-1}{3}} \equiv h \pmod \pi \iff 2^{\frac{p-1}{3}} \equiv h \pmod p$. Note that the hypothesis $\chi_\pi(2) 
e 1$ means that $2$ is not a cubic residue modulo $p$, which is equivalent to $A,B$ odd by Exercise 39. We can conclude

\bigskip

{\it
Suppose that $p \equiv 1 \pmod 6$, and let $(A,B)$ be the unique solution of $4p = A^2 + 27 B^2$ such that $A \equiv 1 \pmod 3$, and $B\equiv A \pmod 4$ if $B$ odd, and $B>0$ otherwise.

If $B$ is even, then $2$ is a cubic residue modulo $p$, and $2^{\frac{p-1}{3}} = 1$.

If $B$ is odd, then $2$ is not a cubic residue modulo $p$, and $B$ satisfies $B \equiv A \pmod 4$.

Writing $a = \frac{A+3B}{2}, b = 3B$, and $\pi = a + b \omega$, then  $\chi_\pi(2) = \omega$, and
$$2^{\frac{p-1}{3}}  \equiv \frac{A+9B}{A-9B} \pmod p.$$
}

\bigskip

The three roots of $x^3 - 1$ in $\F_p$ are $1, \frac{A+9B}{A-9B}, \frac{A-9B}{A+9B}$. Here $2$ is not a cubic residue modulo $p$, and $2^{\frac{p-1}{3}}$ is also a cubic root of unity modulo $p$, so $2^{\frac{p-1}{3}} \equiv  \frac{A\pm 9B}{A\mp9B} \pmod p$. The proposition  explicits the choice of the sign of $B$ which gives $2^{\frac{p-1}{3}}  \equiv \frac{A+9B}{A-9B} \pmod p$.

\bigskip

Numerical example : Let $p$ be the prime $967$. If we decompose $p$ on the form $p = \pi \overline{\pi}$, we obtain $\pi =  a + b \omega = -34 -27 \omega$. To obtain these result without tries, I find $k = 682$ such that $p \mid k^2 + 3$ with the Tonelli-Shanks algorithm, and I compute $\gcd(p, k+1 + 2\omega) = a + b \omega$, where $a + b \omega$ is primary, with a small Python program using the class of elements in $\Z[\omega]$ and the Euclid algorithm in $\Z[\omega]$. This gives the decompositions 
$$967 = p = a^2 -ab + b^2 = 34^2 - 34	imes 27 + 27^2,$$
 and 
 $$3868 = 4p = (2a -b)^2 + 3b^2 = A^2 + 27 B^2 = 41^2 + 27 	imes 9^2,$$
 where $A \equiv 1 \pmod 3$, and I choose the sign of $B$ such that $B \equiv A \pmod 4$. We obtain $A = -41, B = -9$, and $a,b$ must verify $A = 2a-b, B = b/3$.
 
  Then $\chi_\pi(2) = \omega$, where $\pi = -41 - 9 \omega$. In $\F_{967}$, the cubic roots of unity modulo $p$ are $1, 142, 824$: $142^3 \equiv 824^3 \equiv 1 \pmod {967}$. 
  
  Here $(A + 9B) (A - 9B)^{-1} = 142$, and we verify with a fast exponentiation that $2^{\frac{p-1}{3}} = 2^{322} \equiv 142 \pmod {967}.$

I give here an extract of a table obtained with this program, which for each $p$ gives $A,B$ such that $4p = A^2 + 27 B^2, A \equiv 1 \pmod 3$ and such that $B \equiv A \pmod 4$ if $A,B$ odd, and $\pi =a +b \omega$ satisfies $\chi_\pi(2) = \omega$ (or $\chi_\pi(2) = 1$ if $A,B$ even, which corresponds to the case $a\equiv 1, b \equiv 0 \pmod 2$).
$$
\begin{array}{l|l|l|l|l|l|l|l|l}
p    &  A   & B  & \pi = a + b \omega   & a 	ext{\%} 2 & b \% 2 & 2^{\frac{p-1}{3}}\ \% \ p & \frac{A-9B}{A+9B} & \chi_\pi(2)\
\hline
787 & 31 & -9 & 2  -27\omega & 0 & 1 & 379 & 379 &\omega \
811 & -56 & -2 & -31  -6 \omega & 1 & 0 & 1 & 130 & 1 \
823 & -5 & 11 & 14 + 33\omega & 0 & 1 & 648 & 648 & \omega \
829 & 7 & 11 & 20 + 33\omega & 0 & 1 & 125 & 125 & \omega  \
853 & -35 & 9 & -4 + 27\omega & 0 & 1 & 632 & 632 & \omega \
859 & 13 & -11 & -10  -33\omega & 0 & 1 & 260 & 260 & \omega \
877 & -59 & 1 & -28 + 3 \omega& 0 & 1 & 594 & 594 & \omega  \
883 & -47 & -7 & -34  -21\omega & 0 & 1 & 545 & 545 & \omega \
907 & 19 & 11 & 26 + 33\omega & 0 & 1 & 384 & 384 & \omega  \
919 & 52 & -6 & 17  -18\omega & 1 & 0 & 1 & 52 & 1 \
937 & 61 & 1 & 32 + 3\omega & 0 & 1 & 614 & 614 & \omega \
967 & -41 & -9 & -34  -27\omega & 0 & 1 & 142 & 142 & \omega  \
991 & 61 & -3 & 26  -9\omega & 0 & 1 & 113 & 113 & \omega  \
997 & 10 & -12 & -13  -36\omega & 1 & 0 & 1 & 692 & 1 \
\end{array}
$$
As a verification I compute $\chi_\pi(2)$ with a fast exponentiation in $\Z[\omega]$ : $\chi_\pi(2) = 2^{\frac{p-1}{3}} \pmod \pi$.

We obtain the primary prime $\mu$ such that $N(\mu) = p, \chi_\mu(2) = \omega^2$ by taking the conjugate of $\pi$. For instance, with $p = 787$,  $\pi =2 - 27\omega$ satisfies $\chi_\pi(2) = \omega$, therefore $\chi_{\overline{\pi}}(2) = \chi_{29 + 27\omega} = \omega^2$.

The lines where $\chi_{\pi}(2) = 1$, corresponding to the case where $A,B$ are even (or equivalently $a$ odd, $b$ even), give the decomposition ${p = x^2 + 27 y^2}$, ${(x = A/2,y = B/2)}$. For instance $997 = 5^2 + 27	imes 6^2$. If $p$ is prime,
$$\exists x\in \Z, \exists y \in \Z,\  p = x^2 + 27y^2 \iff p\equiv 1 \pmod 3 	ext{ and } \exists a \in \Z,\ 2 \equiv a^3 \pmod p.$$

Exercise 9.41

Answers

Comments

Exercise 9.41

Answers

Comments

Add answer