Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Thank you, these answers are perfect –  user108680 Dec 1 '13 at 1:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.