# Find an integral solution for a polynomial

Given odd prime p that $\binom{-2}{p}=1$, show that there are integers x,y such that $x^2+2y^2=p$.

What i did: I move $2y^2$ to the right, then $x^2=p-2y^2$

If $a^2=-2$ (mod p) then this equation turn into $x=ay$ (mod p)

I don't know how to continue from here, should i just say that a is an integer, so obviously there is an answer? I don't see any restriction on x or y, take y=b, then x is just ab mod p, there are p-1 solutions, that's it?

I don't think it's that easy, I'm thinking of proving it using Minkowski's theorem, but i'm not good with that. Can anyone help me?

-

There are two distinct ways I know of to prove such statements.

Proof 1 (elementary, using Pigeonhole Principle):

Since $(\frac{-2}{p})=1$, there exists $t$ s.t. $t^2 \equiv -2 \pmod{p}$.

Consider the integers $a+tb$, for $0 \leq a, b \leq \lfloor \sqrt{p} \rfloor$. There are $(1+\lfloor \sqrt{p} \rfloor)^2>p$ such integers, so by the Pigeonhole Principle, we have $a+tb \equiv c+td \pmod{p}$ where $(a, b) \not =(c, d)$.

Thus $(a-c) \equiv t(d-b) \pmod{p}$ so $(a-c)^2 \equiv t^2(d-b)^2 \equiv -2(d-b)^2$, so $p \mid (a-c)^2+2(d-b)^2$.

Since $(a, b) \not =(c, d)$, we have $(a-c)^2+2(d-b)^2>0$. Also, $|a-c|, |b-d| \leq \lfloor \sqrt{p} \rfloor<\sqrt{p}$ so $(a-c)^2+2(d-b)^2<(\sqrt{p})^2=3p$.

Therefore $(a-c)^2+2(d-b)^2=p, 2p$.

If $(a-c)^2+2(d-b)^2=p$, we are done. If $(a-c)^2+2(d-b)^2=2p$, then $2 \mid (a-c)^2$ so $2 \mid a-c$, so $(d-b)^2+2(\frac{a-c}{2})^2=p$, so we are done. Therefore we can always find integers $x, y$ s.t. $x^2+2y^2=p$.

Proof 2 (Using binary quadratic forms):

Again, since $(\frac{-2}{p})=1$, there exists $t$ s.t. $t^2 \equiv -2 \pmod{p}$. We may write $t^2+2=kp$ for some integer $k$.

Observe that the binary quadratic form $px^2+2txy+ky^2$ represents $p$. It has discriminant $(2t)^2-4kp=-8$. We may apply Gauss reduction to get an equivalent reduced form $ax^2+bxy+cy^2$, where $-a<b \leq a<c$ or $0 \leq b \leq a=c$, and discriminant $b^2-4ac=-8$.

Note that $8=4ac-b^2 \geq 4a^2-a^2=3a^2$ so $a=1$. Also $|b| \leq a=1$ and $b$ is even, so $b=0$, and we get $c=2$. Thus the reduced form $x^2+2y^2$ is equivalent to the quadratic form $px^2+2txy+ky^2$, hence represents the same numbers, hence in particular represents $p$. Therefore there are integers $x, y$ s.t. $x^2+2y^2=p$.

-
Thank you, these answers are perfect –  user108680 Dec 1 '13 at 1:48