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

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}$

• Maybe it's just my opinion, but I don't think using $\Bbb Z[\sqrt{2}]$ is an overkill. Showing that $\Bbb Z[\sqrt{2}]$ is a unique factorization domain is very elementary and easy. But I understand that you might want to see a different proof :) – Wojowu May 18 '16 at 16:34
• @Wojowo Is there some way of staying within the finite field and using the square roots of $2$ in that field to construct $a$ and $b$? I am skeptical that one has to go through $\mathbb{Z}$ and the extension $\mathbb{Z}[\sqrt{2}]$ to arrive at this result. Or maybe I am wrong. I was just hoping there's a direct elegant way of seeing it. – BharatRam May 18 '16 at 16:40

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$$

• Could you clarify why $0 < x,y < \sqrt{p}$? I mean, why should there exist $x,y$ both being less than $\sqrt{p}$? – BharatRam May 18 '16 at 16:50
• @BharatRam It's a direct application of Thue's Lemma which follows via PHP. Click on the link. – S.C.B. May 18 '16 at 16:51
• @BharatRam, Oops, and I also made a mistake. See the edit I made. – S.C.B. May 18 '16 at 16:52
• Lovely! I didn't know of Thue's lemma. Seems peculiar and almost tailor-made for this result. Thanks so much for introducing me to this lemma. Will read more on that. Also, thanks for the elegant proof. – BharatRam May 18 '16 at 16:56

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.