Express a prime $p$ as $p=a^2-2b^2$

Question

Suppose $2$ is a quadratic residue modulo $p$ for an odd prime $p$. That is, there is an element $u$ such that $u^2 \equiv 2 \pmod{p}$.

From here, can we prove that there exist integers $a$ and $b$ such that $$a^2-2b^2=p$$ Its the equality part that is tricky. It is trivial to produce $a,b$ where $a^2-2b^2 \equiv 0 \pmod{p}$, for example when $a=u, b=1$. Is there some way of starting with $(u,1)$ and constructing $(a,b)$ from it? If not constructing algorithmically, is there at least an existential argument?

This is related to the problem of finding for which primes $p$ is $2$ a quadratic residue. If we can prove the above, then from the form of $p=a^2-2b^2$, it is easy to see that $p=8k \pm 1$. I know a proof which uses quadratic fields. It shows that $p$ cannot be prime in $\mathbb{Z}[\sqrt{2}]$ and thus it is of the form $p=(a+\sqrt{2}b)(a-\sqrt{2}b)$. However, it seems (to me) like an overkill to use non-trivial results from quadratic fields for this. Surely there's got to be an elegant method which stays within $\mathbb{Z}/p\mathbb{Z}$

Answer 1

I don't know much about field theory but within the laws of elementary mathematics, note that by Thue's Lemma we have $$x \equiv uy \pmod p$$ For $u^2 \equiv 2 \pmod p$, such that $0<|x|,|y|<\sqrt{p}$. Then proceed to notice $$x^2-2y^2 \equiv 0 \pmod p$$ Then notice $$-2p<x^2-2y^2<p$$ So $x^2-2y^2=0$ or $x^2-2y^2=-p$. I believe you can proceed from here.

If you actually want to see the full solution, pass your mouse over the yellow area.

$x^2-2y^2=0$ is clearly impossible over the integers. If $x^2-2y^2=-p$, then $$(2y-x)^2-2(y-x)^2=2y^2-x^2=p$$

Answer 2

This is a general algorithm to take a prime, in particular an odd prime $p,$ and express it as the value of an indefinite binary form of discriminant $\Delta.$ The requirements are that $\Delta > 0,$ that $\Delta $ is NOT a perfect square, and that $\Delta$ is a quadratic residue $\pmod p.$ In particular, $p$ does not divide $\Delta.$ With large class number, this method also tells us which forms represent $p,$ as any prime is represented either by one $SL_2 \mathbb Z$ equivalence class of forms of a specified discriminant $\Delta,$ or by a class and its opposite class. This algorithm is very fast once programmed, similar to the Euclidean algorithm. As a fairly difficult example, take some prime $p$ such that $(257|p) = 1.$ Then $p$ is represented either by the principal form $\langle 1, 15, -8 \rangle,$ or by both of a pair of opposite forms, $\langle 2, 15, -4 \rangle$ and $\langle 4, 15, -2 \rangle.$ Deciding which is the stuff of Class Field Theory, but we can find out, for a specific prime, with the algorithm below. Well, why not. A prime $p$ other than $257$ can be expressed as $p = u^2 + 15 uv - 8v^2$ if and only if $x^3 - x^2 - 4x+3$ has three distinct roots $\pmod p.$ We also have $x^3 - x^2 - 4x+3 \equiv (x+9)^2 (x + 238) \pmod {257},$ and $257$ is also represented by $ u^2 + 15 uv - 8v^2.$ A prime $p,$ including $2,$ is represented as $p = 2u^2 + 15 uv - 4v^2$ if and only if $x^3 - x^2 - 4x+3$ is irreducible $\pmod p.$ Oh, $x^3 - x^2 - 4x+3$ has exactly one root $\pmod p$ when $(257|p) = 1.$ Since the Fermat prime $257 \equiv 1 \pmod 4,$ we also have $(257|p) = (p|257).$

$$ (2u)^2 \equiv 8 \pmod {4p}, $$ $$ (2u)^2 = 8 + 4pt $$ for an integer $t.$ This means that the binary quadratic form $\langle p, 2u, t \rangle,$ or $$ f(x,y) = p x^2 + 2 u xy + t y^2, $$ has discriminant $8.$

Reduction of this form to a Gauss-Lagrange "reduced" form takes a finite number of steps. There is just one equivalence class of forms of this discriminant, and just two reduced forms, $\langle 1,2,-1 \rangle$ and $\langle -1,2,1 \rangle.$

The process of reduction, done carefully, results in an integer matrix $P$ of determinant $1$ such that, for example, $P^T HP = G,$ where $$ H = \left( \begin{array}{rr} p & u \\ u & t \end{array} \right) $$ and, as one of the two choices, $$ G = \left( \begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array} \right) $$ We then have $Q = P^{-1}$ is also an integer matrix of determinant $1,$ and $$ Q^T GQ = H. $$ The left hand column of $Q$ tells us how to represent $p$ as $a^2 + 2ab - b^2.$

Probably worth it: reduction is a finite sequence of steps, beginning with $H_0 = H$ and $H_{j+1} = R_j^T H_j R_j,$ finally some $H_N = G$ is reduced. A careful reading of the Buell pages reveals that we always have $$ R_j = \left( \begin{array}{rr} 0 & -1 \\ 1 & \delta_j \end{array} \right) $$ with integer $\delta_j.$ The bookkeeping part is $P = R_0 R_1 R_2 \cdots R_{N-1}.$

Oh, before I forget, it turns out that an indefinite form $\langle A,B,C \rangle$ is reduced if and only if BOTH $AC<0$ and $B>|A+C|.$ This is a minor note in a book in preparation by Franz Lemmermeyer. Here we go, Gauss reduced forms are Theorem 1.36, pdf page 43 but book numbered page 37. The condition I give above is formula (1.34).

I made jpegs of the three most important pages in BUELL as relates to reduction of indefinite binary forms.