4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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 :) $\endgroup$ – Wojowu May 18 '16 at 16:34
  • $\begingroup$ @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. $\endgroup$ – BharatRam May 18 '16 at 16:40
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you clarify why $0 < x,y < \sqrt{p}$? I mean, why should there exist $x,y$ both being less than $\sqrt{p}$? $\endgroup$ – BharatRam May 18 '16 at 16:50
  • $\begingroup$ @BharatRam It's a direct application of Thue's Lemma which follows via PHP. Click on the link. $\endgroup$ – S.C.B. May 18 '16 at 16:51
  • $\begingroup$ @BharatRam, Oops, and I also made a mistake. See the edit I made. $\endgroup$ – S.C.B. May 18 '16 at 16:52
  • $\begingroup$ 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. $\endgroup$ – BharatRam May 18 '16 at 16:56
3
$\begingroup$

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.

enter image description here enter image description here enter image description here

$\endgroup$

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.